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

The message says that you have mismatched levels of list nesting. Try adding an explicit type signature to your function; then GHC will know what you intended the type to be, and might be able to give you a better idea where the error is. — MathematicalOrchid
– MathematicalOrchid, Commented Sep 30, 2015 at 8:31
My personal theory is that you don't need the square brackets in map (\x -> [(take n ys)]:x), but I haven't checked that. — MathematicalOrchid
– MathematicalOrchid, Commented Sep 30, 2015 at 8:32
just for the record: the definition of subdivideList in your Python code is missing. — Erik Kaplun
– Erik Kaplun, Commented Sep 30, 2015 at 9:52

Erik Kaplun · Accepted Answer · 2015-09-30 22:59:17Z

9

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.

edited Sep 30, 2015 at 22:59

answered Sep 30, 2015 at 9:44

Erik Kaplun

38.5k15 gold badges102 silver badges113 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Brian Yeh Over a year ago

This is a good answer. The problem is when I run the corrected code with [(take n ys)]:x replaced with (take n ys):x it does not compile for me. Additionally I think doing so will yield incorrect results. This part of the haskell, "[(take n ys)]:x", was translated from "[xs[:i]] + j" in the python code (which is verified to work). I am literally doing a one to one transformation from python to a haskell tail recursive iteration. That's what bugs me about this code. What's even more strange is that the error message mentions infinite type. Most answers haven't addressed that.

Erik Kaplun Over a year ago

I did not say replace with (take n ys):x but take n ys. but also that doesn't mean the code will then do what you expect. try e.g. take n ys ++ x. you are the one who understands the domain, I only provided generic, type related help.

Erik Kaplun Over a year ago

FYI: the : prepends an ELEMENT to a list; it is not list concatenation (++ in Haskell == + in Python).

Brian Yeh · Accepted Answer · 2015-09-30 14:15:56Z

0

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)

The code above will work. The mistake is largely because I'm using (:) when a (++) is more appropriate. Erik Allik really helped me out in deriving this answer so please direct your points towards him as his explanation of debugging haskell and pointing out (++) instead of (:) was equivalent to pythons (+) was instrumental in helping me solve this problem.

answered Sep 30, 2015 at 14:15

Brian Yeh

3,2953 gold badges31 silver badges47 bronze badges

3 Comments

Erik Kaplun Over a year ago

you can just accept my answer instead of redirecting the votes :)

Brian Yeh Over a year ago

Your answer isn't the final or correct answer though. Edit: I did it anyway. Thanks.

Erik Kaplun Over a year ago

well actually it is the correct answer: your question was WHY the error was occurring not what the working solution is, just for the record.

Collectives™ on Stack Overflow

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

2 Answers 2

3 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related