Ошибка бесконечного типа в haskell при попытке перевести функцию python в haskell. Зачем?

Question

def get_N_Partition_Permutations(xs, n): 
    if n == 1: 
     return [[xs]] 
    acc = [] 
    for i in xrange(1,len(xs)): 
     acc += [[xs[:i]] + j for j in get_N_Partition_Permutations(xs[i:], n-1)] 
    return acc 

Я пытаюсь реализовать вышеприведенную функцию (которая находится на Python) в haskell ниже.

getNPartitionPermutations :: [a] -> Int -> [[[a]]] 
getNPartitionPermutations xs 1 = [[xs]] 
getNPartitionPermutations xs n = iter xs 1 [] 
    where iter ys i acc 
      | length xs == i = acc 
      | otherwise  = 
       iter ys (i+1) (elem':acc) 
       where elem' = map (\x -> [(take i ys)]:x) rec' 
         rec' = getNPartitionPermutations (drop i ys) (n-1) 

У меня возникает странная ошибка, которую я не совсем понимаю. Почему этот код работает в python, но не в haskell? Сообщение об ошибке ниже

partitionArr.hs|23 col 104 error| Occurs check: cannot construct the infinite type: a ~ [[a]] 
Expected type: [[[a]]] 
Actual type: [a] 
Relevant bindings include 
    acc :: [[[[[a]]]]] (bound at partitionArr.hs:21:19) 
    ys :: [a] (bound at partitionArr.hs:21:14) 
    iter :: [a] -> GHC.Types.Int -> [[[[[a]]]]] -> [[[[[a]]]]] (bound at partitionArr.hs:21:9) 
    xs :: [[[a]]] (bound at partitionArr.hs:20:27) 
    getNPartitionPermutations :: [[[a]]] -> GHC.Types.Int -> [[[[[a]]]]] 
    (bound at partitionArr.hs:19:1) 
    In the first argument of ‘Algo.getNPartitionPermutations’, 
    namely ‘(GHC.List.drop n ys)’ 
    In the second argument of ‘(GHC.Base.$!)’, 
    namely ‘Algo.getNPartitionPermutations (GHC.List.drop n ys) (n 
    GHC.Num.- 1)’ 

partitionArr.hs|20 col 39 error| Occurs check: cannot construct the infinite type: a ~ [[a]] 
Expected type: [a] 
Actual type: [[[a]]] 
Relevant bindings include 
    iter :: [a] -> GHC.Types.Int -> [[[[[a]]]]] -> [[[[[a]]]]] (bound at partitionArr.hs:21:9) 
    xs :: [[[a]]] (bound at partitionArr.hs:20:27) 
    getNPartitionPermutations :: [[[a]]] -> GHC.Types.Int -> [[[[[a]]]]] 
    (bound at partitionArr.hs:19:1) 

In the first argument of ‘iter’, namely ‘xs’In the expression: iter xs 1 [] 

Редактировать: Потому что я не был чист. Функция python возвращает все возможные n разделов списка. поэтому параметры [1,2,3,4], 2 дают [[[1], [2,3,4]], [[1,2], [3,4]], [[1,2,3] ] [4]]]

тип подписи функции Haskell является [а] -> Int -> [[[а]]]

Answer 1

Прежде всего, я сделал ваш Haskell код немного более понятным:

getNPartitionPermutations :: [a] -> Int -> [[[a]]] 
getNPartitionPermutations xs 1 = [[xs]] 
getNPartitionPermutations xs n = iter xs 1 [] 
     where iter ys n acc 
       | length xs == n = acc 
       | otherwise  = 
        iter ys (n+1) (elem:acc) 
        where elem = map (\x -> [(take n ys)]:x) rec' 
          rec' = getNPartitionPermutations (drop n ys) (n-1) 

похоже, проблема типа исходит из этого выражения в определении elem:

[(take n ys)]:x 

если вы замените его head x или take n ys или take n ys ++ x, код компилируется. Это означает, что каким-то образом вы предоставляете значение типа [[[a]]] вместо значения типа [a]. То есть у вас есть 2 дополнительных обертки с [].

И хотя я не нашел времени, чтобы полностью понять, что должен делать ваш код, я вполне уверен, что эти подсказки вы можете выяснить, где проблема.

EDIT: проблема заключалась в использовании : вместо ++, а также ненужная упаковка в [take n ys], поэтому заменяя take n ys ++ x это путь. (Только включение в комментарии в ответ)

---

Общие рекомендации:

Путь идти об отслеживании/выявлении ошибок типа является первым рефакторинга кода, как я сделал, т.е. раздробления больших выражений и давая имена подвыражениям, поэтому их значения становятся более заметными и поэтому вы можете временно заменить определенные части общего выражения undefined, потому что undefined имеет любой тип, который вам нравится, и, таким образом, вы можете получить свой код для компиляции без необходимости выяснять все это за один раз. Например, это когда я в конечном итоге, прежде чем пытаться head x и take n ys (обратите внимание на (\x -> undefined) бит):

getNPartitionPermutations :: [a] -> Int -> [[[a]]] 
getNPartitionPermutations xs 1 = [[xs]] 
getNPartitionPermutations xs n = iter xs 1 [] 
     where iter ys n acc 
       | length xs == n = acc 
       | otherwise  = 
        iter ys (n+1) (elem:acc) 
        where elem = map (\x -> undefined) rec' 
          rec' = getNPartitionPermutations (drop n ys) (n-1) 

- это наибольшее подмножество исходного кода, который до сих пор скомпилированного.

А до этого у меня было:

getNPartitionPermutations :: [a] -> Int -> [[[a]]] 
getNPartitionPermutations xs 1 = [[xs]] 
getNPartitionPermutations xs n = iter xs 1 [] 
     where iter ys n acc = undefined 

, после чего я постепенно начал реинтродукции оригинальные биты, перемещая undefined немного дальше вниз по дереву кода:

getNPartitionPermutations :: [a] -> Int -> [[[a]]] 
getNPartitionPermutations xs 1 = [[xs]] 
getNPartitionPermutations xs n = iter xs 1 [] 
     where iter ys n acc 
       | length xs == n = acc 
       | otherwise  = undefined 

затем

getNPartitionPermutations :: [a] -> Int -> [[[a]]] 
getNPartitionPermutations xs 1 = [[xs]] 
getNPartitionPermutations xs n = iter xs 1 [] 
     where iter ys n acc 
       | length xs == n = acc 
       | otherwise  = 
        iter ys (n+1) (elem:acc) 
        where elem = undefined 
          rec' = undefined 

и так далее.

Answer 2

getNPartitionPermutations :: Num a => [a] -> Int -> [[[a]]] 
getNPartitionPermutations xs 1 = [[xs]] 
getNPartitionPermutations xs n = iter xs 1 [] 
     where iter ys i acc 
       | length xs == i = acc 
       | otherwise  = 
        iter ys (i+1) (elem' ++ acc) 
        where elem' = map (\x -> take i ys : x) rec' 
          rec' = getNPartitionPermutations (drop i ys) (n-1) 

Код выше будет работать. Ошибка во многом связана с тем, что я использую (:), когда более подходит (++). Эрик Алик действительно помог мне в этом ответе, поэтому, пожалуйста, направьте свои точки на него, поскольку его объяснение отладки haskell и указание (++) вместо (:) было эквивалентно питонам (+) помогло мне решить эту проблему ,