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

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

I'm trying to implement the function above (which is in Python) in haskell below.

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)

I'm getting a strange error that I don't fully understand. Why does this code work in python but not in haskell? The error message is below

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 []

Edit: Because I wasn't clear. What the python function does is return all possible n partitions of a list. so parameters [1,2,3,4],2 gives [[[1],[2,3,4]],[[1,2],[3,4]],[[1,2,3][4]]]

type signature of the haskell function is [a] -> Int -> [[[a]]]

Answer 1

First of all, I've made your Haskell code a little bit more comprehensible:

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)

It looks like the type problem is coming from this expression in the definition of elem:

[(take n ys)]:x

if you replace it with head x or take n ys or take n ys ++ x, the code compiles. This indicates that somehow you are providing a value of type [[[a]]] instead of a value of type [a]. That is, you have 2 extra wrappings with [].

And whereas I didn't take the time to fully understand what your code is meant to do, I'm quite sure given these hints you can figure out where the problem is.

EDIT: the problem was the use of : instead of ++, as well as the unnecessary wrapping in [take n ys], so replacing with take n ys ++ x is the way to go. (just incorporating the comments into the answer)

---

General advice:

The way to go about tracking down/pinpointing type errors is by first refactoring the code the way I did, i.e. splitting up large expressions and giving names to subexpressions so their meanings become more visible and so you could temporarily replace certain parts of the overall expression with undefined, because undefined has any type you like and thus allows you to get your code to compile without having to figure out all of it in one go. For example, this is where I ended up before trying head x and take n ys (note the (\x -> undefined) bit):

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)

— this was the largest subset of the original code that still compiled.

And before that, I had:

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

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

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

then

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

and so on.