haskellfunctional-programmingdot-operator

Haskell function composition - wrongly inferred type

In the following Haskell code, the function typeError doesn't typecheck.

wrap x = [x]

listf :: [[a]] -> [[a]]
listf = id

typeCheck :: [a] -> [[a]]
typeCheck x = listf (wrap x)

typeError :: [a] -> [[a]]
typeError = wrap . listf

GHC produces this error if it's uncommented:

Couldn't match type `a' with `[a0]'
  `a' is a rigid type variable bound by
      the type signature for typeError :: [a] -> [[a]] at tim.hs:10:1
Expected type: [a] -> [a]
  Actual type: [[a0]] -> [[a0]]
In the second argument of `(.)', namely `listf'
In the expression: wrap . listf

I don't understand why. a should be able to unify with [a0] - they are independent type variables. This is exactly the type it infers for for typeCheck - but not when the . operator is used.

Hugs produces a very similar, and similarly spurious, error message:

ERROR "repro.hs":10 - Inferred type is not general enough
*** Expression    : typeError
*** Expected type : [a] -> [[a]]
*** Inferred type : [[a]] -> [[[a]]]

Furthermore, this works fine:

listf' :: [a] -> [a]
listf' = id

typeCheck' :: [a] -> [[a]]
typeCheck' = wrap . listf'

The problem only occurs with an [[a]] or [[[a]]] or greater. What's the deal here?

Solution

  • You seem to have reversed the function composition here.

    -- This
typeCheck :: [a] -> [[a]]
typeCheck x = listf (wrap x)

-- is the same as
typeCheck' :: [a] -> [[a]]
typeCheck' = listf . wrap

-- while this
typeError :: [a] -> [[a]]
typeError = wrap . listf

-- is the same as
typeError' :: [a] -> [[a]] 
typeError' x = wrap (listf x)

    Now it should hopefully be obvious why this doesn't work. listf requires that its argument is [[a]], but the signature of typeError claims that it works for any [a].