Equivalent functions producing different interpreter results

Question

Reference Information. I study anonymous recursion, and I take on the task of implementing foreplay without using any named recursion to help it sit well in my mind. I'm not quite there yet, and along the way I came across something unrelated, but still interesting.

map1 = \f -> \x -> if (tail x) == [] then [f (head x)] else f (head x) : (map1 f (tail x)) map2 fx = if (tail x) == [] then [f (head x)] else f (head x) : (map2 f (tail x)) map3 f (x:xs) = if xs == [] then [fx] else fx : (map3 f xs) map4 f (x:[]) = [fx] map4 f (x:xs) = fx : map4 f xs 

The GHC complains about the first, excellent with the second, and the third and fourth - just to show how they can be implemented in different ways.

 *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, all this is good.

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

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

Answer 1

You have been bitten by the restriction of monomorphism. All that is written as foo = ... - this means that there are no arguments for the definition, and an explicit type is not specified - for this restriction there must be a non-generic type. The general type in this case, as you said, should have been Eq a => (a -> b) -> [a] -> [b] , but since the restriction of monomorphism applies, both a and b are replaced by () , the simplest type that can be deduced for available type variables.

Answer 2

But if you use unlimited 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 signatures. Only limited types of variables are subject to the restriction of monomorphism .

And if you put the definition of map1 in a file and try to compile it or upload it to 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 about how he did it because he uses ExtendedDefaultRules , otherwise you would get a clear error message.