CODEWITHSUNDEEP
haskell
Kevin Meredith
Kevin Meredith

Reputation: 41939

Split Function - cannot construct the infinite type

The following code fails to compile:

split :: Char -> String -> [String]
split x ys = split' x ys [] 
              where split' _  [] acc = acc
                    split' x (z:zs) acc  
                     | x == z    = acc : split' x zs []
                     | otherwise = split' x zs (z:acc)

Compile-time error:

[1 of 1] Compiling Main             ( Split.hs, interpreted )

Split.hs:5:36:
    Occurs check: cannot construct the infinite type: a0 = [a0]
    In the first argument of `(:)', namely `acc'
    In the expression: acc : split' x zs []
    In an equation for split':
        split' x (z : zs) acc
          | x == z = acc : split' x zs []
          | otherwise = split' x zs (z : acc)
Failed, modules loaded: none.

I read through this helpful post, but I'm not seeing my mistake.

Upvotes: 1

Views: 95

Answers (1)

chi
chi

Reputation: 116174

The posted code defined split' returning acc in one case and acc : <<something>> in another case. The compiler message states that, if a0 is the type of acc, since both cases must return the same type it should be a0 = [a0]. Since no type can satisfy this equation (e.g. String is not [String]), the compiler complains with a type error.

A fix could then be to return a list containing acc is both cases. That is:

split :: Char -> String -> [String]
split x ys = split' x ys [] 
              where split' _  [] acc = [acc]             -- changed
                    split' x (z:zs) acc  
                     | x == z    = acc : split' x zs []
                     | otherwise = split' x zs (z:acc)

As a style note, since x is kept the same in each recursive call, there is no actual need for that parameter.

split :: Char -> String -> [String]
split x ys = split' ys [] 
              where split' [] acc = [acc]
                    split' (z:zs) acc  
                     | x == z    = acc : split' zs []
                     | otherwise = split' zs (z:acc)

The code is now type safe, but it still contains a bug: 

> split 'a' "123a1234a"
["321","4321",""]

This is because the code "pops" characters from the string and "pushes" them in acc, so they end up being reversed. The fix is then easy:

split :: Char -> String -> [String]
split x ys = split' ys [] 
              where split' :: String -> String -> [String]
                    split' [] acc = [reverse acc]
                    split' (z:zs) acc  
                     | x == z    = reverse acc : split' zs []
                     | otherwise = split' zs (z:acc)

In this last revision I also added a type signature for the worker function, to document its code.

Upvotes: 3

Related Questions