Haskell: is it a palindrome?
Thursday, 11th June, 2009
Exercise 5: Write a function that determines whether its input list is a palindrome.
The book website has a lot of interesting discussion re this exercise. Most of it revolves around the best implementation, but there are also queries to do with the correct type signature for the function.
The best implementation in terms of speed, memory use, concision and readibility is given below (alas, I came up with the more long-winded implementation).
ispal x = x == reverse x
But I don’t want to talk about that. I want to talk about type signatures again.
ispal is a function that takes a list and returns a boolean so, naively, I gave my function this type signature:
[A] ispal :: [a] -> Bool ispal x = x == reverse x
ghci gave me the following error message:
Prelude> :load ispal.hs [1 of 1] Compiling Main ( ispal.hs, interpreted ) ispal.hs:2:10: Could not deduce (Eq a) from the context () arising from a use of `==' at ispal.hs:2:10-23 Possible fix: add (Eq a) to the context of the type signature for `ispal' In the expression: x == reverse x In the definition of `ispal': ispal x = x == reverse x Failed, modules loaded: none.
The correct type signature is as follows:
[B] ispal :: (Eq a) => [a] -> Bool ispal x = x == reverse x
So: What is (Eq a)? What is “context”?
RWH hasn’t told us about (Eq a) yet, and the term is not in the index. Maybe it’ll turn up later in the book, maybe it won’t. Who knows? It can be a nice surprise. Ditto “context”.
In the meantime, Learn You a Haskell and A Gentle introduction to Haskell both explain it well, the latter in more technical language than the former, but they’re saying the same thing (see references below).
The “=>” symbol is a class constraint . The left hand side is a constraint on the right hand side. “Context” is the Haskell technical term for this kind of contraint .
In the type signature above, the constraint/context is that the types a must be of type Eq. Items of type Eq support equality testing .
So, in the definition of ispal, the use of “==” forces the interpreter to check that x is of type Eq. If there is no type signature, then ghci is free to infer that x is of type Eq. If there is an explicit type signature, then ghci must follow that. In the type signature in [A] above, there are no contraints on a, so ghci cannot infer that a is always of type Eq. And so we get an error.
I must say I’m glad these two web books are available, to help me over the deficiencies of RWH.