Equivalent functions producing different interpreter results

Question

Background: I'm investigating anonymous recursion, and I'm taking on the challenge of implementing the prelude without using any named recursion just to help it all sit nicely in my mind. I'm not quite there yet, and along the way I've run into something unrelated but still interesting.

map1     = \f -> \x -> if (tail x) == [] 
                       then [f (head x)] 
                       else f (head x) : (map1 f (tail x))

map2 f x =             if (tail x) == [] 
                       then [f (head x)] 
                       else f (head x) : (map2 f (tail x))

map3 f (x:xs) = if xs == [] then [f x] else f x : (map3 f xs)

map4 f (x:[]) = [f x]
map4 f (x:xs) =  f x : map4 f xs

GHC complains about the first one, is fine with the second and the third and fourth ones are there just to show how they could be implemented differently.

*Main> map1 (*2) [1..10]

<interactive>:1:15:
    No instance for (Num ())
      arising from the literal `10'
    Possible fix: add an instance declaration for (Num ())
    In the expression: 10
    In the second argument of `map1', namely `[1 .. 10]'
    In the expression: map1 (* 2) [1 .. 10]
*Main> map2 (*2) [1..10]
[2,4,6,8,10,12,14,16,18,20]
*Main> map3 (*2) [1..10]
[2,4,6,8,10,12,14,16,18,20]
*Main> map4 (*2) [1..10]
[2,4,6,8,10,12,14,16,18,20]

If I add a type signature to map1 it's all good.

map1 :: Eq a => (a -> b) -> [a] -> [b]

The first two functions seem pretty much the same to me, so I suppose my question is simply "What's going on here?"

Answer 1

You were bitten by the monomorphism restriction. Anything that is written as foo = ... - meaning that there are no arguments to the definition, and no explicit type is given - has to have a non-generic type according to this restriction. The generic type in this case would, as you said, have had to be Eq a => (a -> b) -> [a] -> [b], but since the monomorphism restriction applies, both a and b are replaced by (), the simplest type that can be inferred for the available type variables.

Answer 2

But, if you use the unconstrained null instead of (== []),

Prelude> let map0 = \f -> \x -> if null (tail x) then [f (head x)] else f (head x) : map0 f (tail x)
Prelude> :t map0
map0 :: (a -> t) -> [a] -> [t]
Prelude> map (*2) [1 .. 10]
[2,4,6,8,10,12,14,16,18,20]

it works without arguments or a signature. Only constrained type variables are subject to the monomorphism restriction.

And if you put the definition of map1 into a file and try to compile it or load it into ghci,

Ambiguous type variable `a0' in the constraint:
  (Eq a0) arising from a use of `=='
Possible cause: the monomorphism restriction applied to the following:
  map1 :: forall t. (a0 -> t) -> [a0] -> [t] (bound at Maps.hs:3:1)
Probable fix: give these definition(s) an explicit type signature
              or use -XNoMonomorphismRestriction
In the expression: (tail x) == []
In the expression:
  if (tail x) == [] then
      [f (head x)]
  else
      f (head x) : (map1 f (tail x))
In the expression:
  \ x
    -> if (tail x) == [] then
           [f (head x)]
       else
           f (head x) : (map1 f (tail x))

ghci only complained in the way it did because it uses ExtendedDefaultRules, otherwise you would have gotten an understandable error message.