CODEWITHSUNDEEP
haskell
Petras Purlys
Petras Purlys

Reputation: 1155

How does Haskell compiler infer these (list of lists) types?

I'm trying to create a function that packs equal elements to a list. This is a training problem so I want to make my own sollution to work. I'm not looking for alternative ways to solve the problem, I would just like to understand why this code does not compile.

Here's the function:

pack :: Eq a => [a] -> [[a]]
pack xs = let packHelper acc [] = acc
              packHelper acc zs = let splitOff = takeWhile (\y -> y == (head zs)) zs
                                  in  packHelper ( (splitOff:acc) (drop (length splitOff) zs) )
          in  packHelper [[]] xs

And the test case:

pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e']
==
["aaaa","b","cc","aa","d","eeee"]

The current implementation does not compile and gives this error:

main.hs:109:15: error:
* Couldn't match type `[a1] -> [[a1]]' with `[[a1]]'
  Expected type: [[a1]] -> [[a1]]
    Actual type: [[a1]] -> [a1] -> [[a1]]
* In the expression:
    let
      packHelper acc [] = acc
      packHelper acc zs
        = let ...
          in packHelper ((splitOff : acc) (drop (length splitOff) zs))
    in packHelper [[]] xs
  In an equation for `pack':
      pack xs
        = let
            packHelper acc [] = acc
            packHelper acc zs = ...
          in packHelper [[]] xs
* Relevant bindings include
    packHelper :: [[a1]] -> [[a1]]
      (bound at main.hs:109:15)
    |
109 | pack xs = let packHelper acc [] = acc
    |               ^^^^^^^^^^^^^^^^^^^^^^^^...

main.hs:111:52: error:
* Couldn't match expected type `[a1] -> [[a1]]'
              with actual type `[[a1]]'
* The function `splitOff : acc' is applied to one argument,
  but its type `[[a1]]' has none
  In the first argument of `packHelper', namely
    `((splitOff : acc) (drop (length splitOff) zs))'
  In the expression:
    packHelper ((splitOff : acc) (drop (length splitOff) zs))
* Relevant bindings include
    splitOff :: [a1]
      (bound at main.hs:110:39)
    zs :: [a1]
      (bound at main.hs:110:30)
    acc :: [[a1]]
      (bound at main.hs:110:26)
    packHelper :: [[a1]] -> [[a1]]
      (bound at main.hs:109:15)
    |
111 |                                   in  packHelper ( (splitOff:acc) 
(drop (length splitOff) zs) )
    |                                                    
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

main.hs:112:15: error:
* Couldn't match expected type `[a] -> [[a]]'
              with actual type `[[a0]]'
* The function `packHelper' is applied to two arguments,
  but its type `[[a0]] -> [[a0]]' has only one
  In the expression: packHelper [[]] xs
  In the expression:
    let
      packHelper acc [] = acc
      packHelper acc zs
        = let ...
          in packHelper ((splitOff : acc) (drop (length splitOff) zs))
    in packHelper [[]] xs
* Relevant bindings include
    xs :: [a]
      (bound at main.hs:109:6)
    pack :: [a] -> [[a]]
      (bound at main.hs:109:1)
    |
112 |           in  packHelper [[]] xs 
    |               ^^^^^^^^^^^^^^^^^^

Why does the compiler expect [[a1]] -> [[a1]] and not [[a1]] -> [a1] -> [[a1]] for packHelper?

Upvotes: 1

Views: 48

Answers (1)

phadej
phadej

Reputation: 12123

The problematic part is:

in  packHelper ( (splitOff:acc) (drop (length splitOff) zs) )

Note: you have parentheses around both supposed packHelper arguments. Fix is easy:

in  packHelper (splitOff:acc) (drop (length splitOff) zs)

Then packHelper is applied to two arguments and type-checking works out.

The type-error you see is caused by GHC trying to unify

-- infered from last `in`
-- - [[]] is `[[a1]`` "some" list-of-lists
-- - [a] is the type of xs
-- - [[a]] is the result type of `pack`
packHelper :: [[a]] -> ([a] -> [[a]])

with

-- because in inner `in` packHelper is applied to one argument only,
-- but result should be [[a]], the result type of `pack`
-- first argument can be "something" so far.
packHelper :: b      -> [[a]]

So GHC get's missmatch between [a] -> [[a]] and [[a]] which it reports.

In general such errors "a -> b doesn't match b" are usually a sign that you forgot to apply an argument.

Upvotes: 2

Related Questions