CODEWITHSUNDEEP
haskell
Frank
Frank

Reputation: 4417

Surprising function signature in Haskell

I am a Haskell newbie, please forgive me for asking this which might be obvious, but I am surprised by this: 

len2 :: [a] -> Int
len2 xx = if xx == [] then 0 else 1 + (len2 (tail xx))

gives me:

No instance for (Eq a) arising from a use of ‘==’
Possible fix:
  add (Eq a) to the context of
    the type signature for len2 :: [a] -> Int
In the expression: xx == []

I am surprised because I thought Haskell could tell whether a list was [] or not without looking at any element (in C++, I would see that the list has size 0 and leave it at that, for example).

Upvotes: 2

Views: 70

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 153182

The type of (==) in this case is Eq a => [a] -> [a] -> Bool. Hopefully you agree that before you see any arguments the Eq a constraint makes sense: if you want to check two arbitrary lists are equal, you have to know how to check if elements are equal. You might wish that once you applied (==) to the concrete argument [] that the Eq a constraint wasn't needed, but this is actually quite a subtle thing to notice. Perhaps partial evaluation would be able to produce a function that didn't have the constraint. But extant implementations do not try to do this analysis; they keep the conservative type Eq a => [a] -> Bool which has discharged an [a] argument but not the Eq a constraint.

Some options:

  1. Use null :: [a] -> Bool instead of (==[]).

    len2 xx = if null xx then ... else ...

  2. Pattern match, thus:

    len2 []     = ...
len2 (x:xs) = ...

    As a bonus, this way you can avoid calling the nasty tail function.

I would say choice (2) is significantly more idiomatic.

Upvotes: 9

Related Questions