algorithm - infinite type error in haskell when trying to translate python function into haskell. Why? -

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

i'm trying implement function above (which in python) in haskell below.

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

i'm getting strange error don't understand. why code work in python not in haskell? error message below

partitionarr.hs|23 col 104 error| occurs check: cannot construct infinite type: ~ [[a]] expected type: [[[a]]] actual type: [a] relevant bindings include   acc :: [[[[[a]]]]] (bound @ partitionarr.hs:21:19)   ys :: [a] (bound @ partitionarr.hs:21:14)   iter :: [a] -> ghc.types.int -> [[[[[a]]]]] -> [[[[[a]]]]] (bound @ partitionarr.hs:21:9)   xs :: [[[a]]] (bound @ partitionarr.hs:20:27)   getnpartitionpermutations :: [[[a]]] -> ghc.types.int -> [[[[[a]]]]]   (bound @ partitionarr.hs:19:1)   in first argument of ‘algo.getnpartitionpermutations’,     namely ‘(ghc.list.drop n ys)’   in 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 infinite type: ~ [[a]] expected type: [a] actual type: [[[a]]] relevant bindings include   iter :: [a] -> ghc.types.int -> [[[[[a]]]]] -> [[[[[a]]]]] (bound @ partitionarr.hs:21:9)   xs :: [[[a]]] (bound @ partitionarr.hs:20:27)   getnpartitionpermutations :: [[[a]]] -> ghc.types.int -> [[[[[a]]]]]   (bound @ partitionarr.hs:19:1)  in first argument of ‘iter’, namely ‘xs’in expression: iter xs 1 [] 

edit: because wasn't clear. python function return possible n partitions of list. parameters [1,2,3,4],2 gives [[[1],[2,3,4]],[[1,2],[3,4]],[[1,2,3][4]]]

type signature of haskell function [a] -> int -> [[[a]]]

first of all, i've made haskell code little bit more comprehensible:

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

it looks type problem coming expression in definition of elem:

[(take n ys)]:x 

if replace head x or take n ys or take n ys ++ x, code compiles. indicates somehow providing value of type [[[a]]] instead of value of type [a]. is, have 2 wrappings [].

and whereas didn't take time understand code meant do, i'm quite sure given these hints can figure out problem is.

edit: problem use of : instead of ++, unnecessary wrapping in [take n ys], replacing take n ys ++ x way go. (just incorporating comments answer)

---

general advice:

the way go tracking down/pinpointing type errors first refactoring code way did, i.e. splitting large expressions , giving names subexpressions meanings become more visible , temporarily replace parts of overall expression undefined, because undefined has type , allows code compile without having figure out of in 1 go. example, ended before trying head x , take n ys (note (\x -> undefined) bit):

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

— largest subset of original code still compiled.

and before that, had:

getnpartitionpermutations :: [a] -> int -> [[[a]]] getnpartitionpermutations xs 1 = [[xs]] getnpartitionpermutations xs n = iter xs 1 []       iter ys n acc = undefined 

after gradually started reintroducing original bits, moving undefined bit further down code tree:

getnpartitionpermutations :: [a] -> int -> [[[a]]] getnpartitionpermutations xs 1 = [[xs]] getnpartitionpermutations xs n = iter xs 1 []       iter ys n acc               | length xs == n = acc               | otherwise      = undefined 

then

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

and on.