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

Haskell type variables

Monday, 1st June, 2009

Real World Haskell
Chapter 3: Defining types, streamlining functions
Section: A More Controlled Approach

-- file:ch03/MySecond.hs
-- edited excerpt

-- safeSecond :: [a] -> Maybe a

safeSecond [] = Nothing
safeSecond xs = if null (tail xs)
                then Nothing
                else Just (head (tail xs))

-- tidySecond :: [a] -> Maybe a

tidySecond (_:x:_) = Just x
tidySecond _       = Nothing

In December, Helge Stenström made an interesting comment about the above code:

If the type declarations using :: are omitted from safeSecond and tidySecond, they have visually different types, at least in ghci.

safeSecond :: [a] -> Maybe a
tidySecond :: [t] -> Maybe t

Why is it so?

In Hugs both functions have the same type [a] -> Maybe a.

The ghci effect is reproduced in simpler code:

safe xs = head xs
tidy (x:_) = x

In ghci:

*Main> :type safe
safe :: [a] -> a
*Main> :type tidy
tidy :: [t] -> t

I asked about this on Haskell-beginners and got some interesting replies (of which my understanding has a comfortable vagueness). Here is the last reply:

On Sun, May 31, 2009 at 05:42:44PM +0200, Daniel Fischer wrote:
>
> But that has nothing to do with the phenomenon, in the inferred type signatures of
> safeSecond and tidySecond, the ‘a’ resp. ‘t’ are both type variables of kind *.
> The only difference is that in one case the name supply delivered ‘a’ and in the other it
> delivered ‘t’.

I think one source of difference is that ghci tries to maintain type
variable names from declared type signatures. So perhaps one of the
library functions used to define ‘safeSecond’ has an explicitly
declared type signature that mentions ‘a’, and a library function used
to defined ‘tidySecond’ has one that mentions ‘t’.

-Brent

Type signatures in Haskell

Monday, 1st June, 2009

From section Record Syntax (p. 55), RWH starts surreptitiously adding type signatures to its code samples. The code samples work just as well without the type signatures, and RWH does not explain why they are being used (in fact, RWH doesn’t mention these code sample type signatures at all).

Haskell is a typed language, but it uses type inference. So why use type signatures at all? RWH waits until Chapter 5, Section Type Inference is a Double-Edged Sword (p. 117) before telling us.

One reason might be that Haskell might not infer the type you want it to infer. Trivial example:

v :: Int
v = 5

Without the type signature, Haskell will infer that v is of type Integer. OK, that probably won’t make any bridges collapse, but a similar false inference with more complex types might.

Maybe Just Nothing

Sunday, 24th May, 2009

Real World Haskell
Chapter 3: Defining types, streamlining functions
Section: Parametrised types

On the first few readings, this section (a single page in the dead tree version) flummoxed me completely. Some of the comments on the book’s web site were helpful, and now I’ve worked through it. This post can bear witness to my journey.

Contents:

  1. Types
  2. Algebraic data types
  3. Parametrised types
  4. Very Important Note
  5. A Use case
  6. Maybe, Just and Nothing
  7. Note also

Read the rest of this entry »

Pattern matching in Haskell

Tuesday, 19th May, 2009

I’m working my way through Real World Haskell. Haskell is an exciting language. The book is … so near and yet so far: it could be an exciting introduction to an exciting language, as well as showing that you can learn ‘real world’ programming and think deeply about the language at the same time… Unfortunately, the current edition (both print and online versions) is extremely shoddy and consequently very annoying.

For example, Chapter 3 “Defining Types, Streamlining Functions” has a section “Pattern Matching” which describes, among other things, how the ordering of function definitions affects the behaviour of the code.

Unfortunately, the example given (reproduced below) works the same whichever way the definitions are ordered.

-- file: rwh/ch03/add.hs
sumList (x:xs) = x + sumList xs
sumList [] = 0

Why couldn’t the authors provide an example that exemplifies their point?

What’s wrong with good old factorial?

This order works properly:

-- file: fact_good.hs
factorial 1 = 1
factorial n = n * factorial (n - 1) -- brackets necessary

The reverse order doesn’t work at all:

-- file: fact_bad.hs
factorial n = n * factorial (n - 1) -- brackets necessary
factorial 1 = 1

Loading and running fact_bad.hs in ghci causes two interesting things:
Read the rest of this entry »