Haskell: is it a palindrome?

Thursday, 11th June, 2009

Real World Haskell
Chapter 3: Defining types, streamlining functions
Section: End of chapter exercises

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 [1]. The left hand side is a constraint on the right hand side. “Context” is the Haskell technical term for this kind of contraint [3].

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 [1].

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.

References

I must say I’m glad these two web books are available, to help me over the deficiencies of RWH.

Learn You a Haskell:
[1] Types and Typeclasses::Typeclasses 101
[2] Making Our Own Types and Typeclasses::Typeclasses 102

A Gentle introduction to Haskell:
[3] Chapter 5: Type classes and overloading

Advertisements

One Response to “Haskell: is it a palindrome?”


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: