Haskell Split List Function Infinite Type Error

Question

I am working on a function in Haskell that will take one list and divide it into two evenly sized lists. Here is what I have:

split (x:y:xs) = split2 ([((length(x:y:xs) `div` 2)-2) : x ++ y] : [xs])
split2 (x:xs:[y:ys]) = split2 ((x-1) : [xs] ++ y : [ys])
split2 (0:xs:[y:ys]) = (xs:[y:ys])

The function takes the first two elements of a list, and puts them together into list #2 and appends the first list as a second element. It then gets the length of the list, and divides it by two to find out how many times to run taking into account the fact that it already removed two elements from the first list. It then takes those two pieces of information and puts it into split2, which takes another element from the first list and appends it to the second list in the first element, also it counts down 1 from the number of runs and then runs again.

Problem is, when I run it I get this:

Functions.hs:19:49:
    Occurs check: cannot construct the infinite type: t0 = [t0]
    In the first argument of `(:)', namely `(y)'

19 refers to line 2, the first split2 function. Not exactly sure how to go about fixing this error. Any ideas?

Answer 1

It's hard to know where to start...

Let's define functions from ever larger chunks of the expression in split2.

f1 (x:y:xs) = (length(x:y:xs) `div` 2)-2
f1 :: [a] -> Int

Ok, so the argument is a list of something, and it returns an Int

f2 (x:y:xs) = ((length(x:y:xs) `div` 2)-2) : x
f2 :: [[Int]] -> [Int]

Here, the length Int is being cons'd with x, so x must be [Int], so (x:y:xs) must be [[Int]]. We can also infer that y has the same type as x, and xs is a list of things of the same type; [[Int]]. So the x ++ y will also be [Int].

So, [xs] will have type [[[Int]]]. Now, we wrap the result in a list constructor, and cons it with [xs]:

f3 (x:y:xs) = [((length(x:y:xs) `div` 2)-2) : x ++ y] : [xs]
f3 :: [[Int]] -> [[[Int]]]

I'm guessing you didn't expect the argument to be a list of lists of lists of Ints.

Now, if we look at split2, the argument pattern (x:xs:[y:ys]) implies that it is of type:

split2 :: [[a]] -> b
     x :: [a]
    xs :: [a]
     y ::  a
    ys :: [a]

The rhs of the first definition of split2 tries to construct a new list by concatenating (x-1) : [xs] and y : [ys]. However, if we substitute the types into the y : [ys], we find:

y : [ys] :: a : [[a]]

But since (:) :: a -> [a] -> [a], this means that [[a]] must be the same type as [a], or a must be a list of itself, which is not possible.

The (x-1) is also badly typed, because it attempts to subtract one from a list.

I can't tell if you want to split the lists into even and odd elements, or into first and second halves.

Here are two versions that split into the first and second halves, rounding down (RD) or up (RU) if the length is odd:

splitRD xs = splitAt (length xs `div` 2) xs
splitRU xs = splitAt ((length xs + 1) `div` 2) xs

Here's a version that splits the list into even and odd elements:

splitEO [] = ([], [])
splitEO [e] = ([e], [])
splitEO (e:o:xs) = (e:es, o:os) where (es, os) = splitEO xs

Answer 2

Few suggestions

• Write types to all the functions. It makes the code more readable and also helps catching errors.

• The type of ++ is [a] -> [a] -> [a] and you are adding length of a list along with elements. Since list has to be of uniform type and length returns Int type, so compiler infers type of split as [[Int]] -> t (assuming split2 returns type t).

• When you pass ([((length(x:y:xs)div2)-2) : x ++ y] : [xs]) to split2. xs is of type [[Int]] which means [xs] is of type [[[Int]]] , so compiler infers type of split2 to [[[Int]]] -> t.

Now in the definition of split2

 split2 (x:xs:[y:ys]) = split2 ((x-1) : [xs] ++ y : [ys])

ys is of type [[Int]], so y is of type [Int]. xs is of type [[Int]], but you are doing [xs] ++ y, which means both [xs] and y should be of same type ( [a] for some a).

Since you have not provided any types compiler is totally confused how to infer such type.

If you simply want to split the list into two equal parts why not do something more simpler like

split3 :: [a] -> ([a], [a])
split3 [] = ([],[])
split3 [x] =  ([x],[])
split3 (x:y:xs) = let (xs',ys') = split3 xs in (x:xs',y:ys')

Answer 3

You seem to be passing state around in a list instead of as values to a function, which creates problems when it seems to the compiler as though you're creating a list of heterogenous values, whereas lists in Haskell are supposed to be of homogenous type.

Instead of

split2 (0:xs:[y:ys])

you should pass the different arguments/values to the function separately like this

split2 n xs (y:ys)

The functionality you're looking for is also reproduced in standard library functions.

halveList xs = splitAt (length xs `div` 2) xs

Answer 4

In Haskell, the elements of a list need to be all of the same type. In your function the lists contain a mixture of Ints, elements of the original list, and sublists of the original list, all of which are probably different types.

You also have some confusion about how to append lists and elements. x ++ y can only be used when x and y are themselves lists, while x : y can only be used when y is a list and x is an element of a list; to make a new list containing x and y as elements instead use [x, y] (although x:[y] also works). Similarly [xs] ++ y needs to be xs ++ [y] instead.

Without changing your basic algorithm, the simplest solution is probably to let split2 take 3 separate arguments.

split (x:y:xs) = split2 ((length(x:y:xs) `div` 2)-2) [x,y] xs
split2 n xs (y:ys) = split2 (n-1) (xs++[y]) ys
split2 0 xs ys = [xs,ys]