Llaisdy

A comment in the discussion on decorate-sort-undecorate in Haskell pointed out to me that my naive and dsu versions of sort by length had different type signatures: the dsu version needlessly required elements of the list to be of type Ord:

sortByLength :: [[a]] -> [[a]]
sortByLength xs = sortBy (comparing length) xs

dsuSortByLength1 :: (Ord a) => [[a]] -> [[a]] 
dsuSortByLength1 xs = map snd (sort (zip (map length xs) xs))

My intention had been that the dsu version have the same requirements as the naive version. So where did this (Ord a) context come from, and how do we get rid of it?

The relevant difference between the functions is the different type signatures for sort and sortBy:

> :type sort
sort :: (Ord a) => [a] -> [a]
> :type sortBy
sortBy :: (a -> a -> Ordering) -> [a] -> [a]

sort requires list elements to be comparable (obviously); sortBy requires only a function that can generate an ordering from its input pair. In dsuSortByLength1 above, the elements of (zip (map length a) a) are required to be of type Ord. We could protest that just because (zip (map length a) a) has to be Ord doesn’t mean that a has to be Ord, but I suspect the compiler is playing on the safe side. [update: see first two comments.]

A function using sortBy instead of sort avoids this extra requirement in the type signature, and shows us a use case for comparing:

sortByLength :: [[a]] -> [[a]]
sortByLength xs = sortBy (comparing length) xs

dsuSortByLength2 :: [[a]] -> [[a]] 
dsuSortByLength2 xs = map snd (sortBy (comparing fst) (zip (map length xs) xs))

Using sortBy (comparing fst) rather than sort allows us to simplfy the type signature.

We can extract length to generalise the function:

sortByFunc :: (Ord a) => (a1 -> a) -> [a1] -> [a1]
sortByFunc f xs = sortBy (comparing f) xs

dsuByFunc  :: (Ord a) => (a1 -> a) -> [a1] -> [a1]
dsuByFunc  f xs = map snd (sortBy (comparing fst) (zip (map f xs) xs))

The (Ord a) context has returned! But here it is just a requirement on the output of the comparison function, which is fine.

I’ve created a new Haskell resources page (see right) to help me keep track of the online resources I use while working through Real World Haskell.

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

Exercise 6: Create a function that sorts a list of lists based on the length of each sublist. (You may want to look at the sortBy function from the Data.List module.)

1. Answering the question
2. Decorate-sort-undecorate
3. Type signatures
4. Further work

Read the rest of this entry »

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

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

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.

• The WikiBook Haskell :: Functional Programming with Types has a nice little section on reasons to use type signatures.
• The tutorial at haskell.org, A Gentle Introduction to Haskell, mentions it in Section 2, Values, Types, and Other Goodies