Thinking Functionally with Haskell (5 page)

getWords :: Int -> [Word] -> [Word]

2.
Take each word and add a label to it. The label consists of the characters of the word, sorted into alphabetical order. For example,
word
is turned into the pair
("dorw","word")
This labelling is achieved by the function
addLabel :: Word -> (Label,Word)

where

type Label = [Char]

3. Sort the list of labelled words into alphabetical order of label, using the function
sortLabels :: [(Label,Word)] -> [(Label,Word)]

4. Replace each group of adjacent labelled words with the same label with a single entry consisting of a pair in which the first component is the common label and the second component is a list of words with that label. This uses a function
groupByLabel :: [(Label,Word)] -> [(Label,[Word])]

5. Replace each entry by a string using a function

showEntry :: [(Label,[Word])] -> String

and concatenate the results.

That gives

anagrams n = concat . map showEntry . groupByLabel .

sortLabels . map addLabel . getWords n

Answer to Exercise G

One possible solution:

Notice that we have omitted to declare the types of the component functions and values in this script. Although Haskell will infer the correct types, it is usually a good idea to put them in for all functions and other values, however simple the types may be. Scripts with explicit type signatures are clearer to read and provide a useful check on the validity of definitions.

If you are interested in the origins of Haskell, you should definitely read
The History of Haskell
, a copy of which is obtainable at
research.microsoft.com/~simonpj/papers/history-of-haskell

One of the abiding strengths of Haskell is that it wasn’t designed to be a closed language, and researchers were encouraged to implement novel programming ideas and techniques by building language extensions or libraries. Consequently, Haskell is a large language and there are numerous books, tutorials and papers devoted to various aspects of the subject, including the recent
Parallel and Concurrent Programming in Haskell
by Simon Marlow (O’Reilly, 2013). Pointers to much of the material can be found at
www.haskell.org
. But three books in particular were open on my desk while writing this text. The first is
Haskell 98, Languages and Libraries, The Revised Report
(Cambridge University Press, 2003), edited by Simon Peyton Jones. This is an indispensable aid in understanding the nitty-gritty of the first standard version of Haskell, called Haskell 98. An online version of the report is available at
www.haskell.org/onlinereport

The present book mostly follows this standard, though it does not cover the whole language by any means.

Since then a new standard, Haskell 2010, has been released; see

haskell.org/onlinereport/haskell2010/

One change is that module names are now hierarchical, so we write
Data.List
rather than just
List
for the library of list utilities.

The second two are textbooks:
Real World Haskell
(O’Reilly, 2009) by Bryan O’Sullivan, John Goerzen and Don Stewart; and
Programming in Haskell
(Cambridge, 2007) by Graham Hutton. As its name implies, the former deals mostly with highly practical applications, while the latter is another introductory text. Graham Hutton did suggest to me, albeit with a grin, that my book should be called
Ivory Tower Haskell
.

There is a fascinating history concerning the common words problem. Jon Bentley invited one programmer, Don Knuth, to write a literate WEB program for the problem, and another programmer, Doug McIlroy, to write a literary review of it. The result was published in Bentley’s
Programming Pearls
column in
Communications of the ACM
, vol. 29, no. 6 (June 1986).

In Haskell every
wellformed
expression has, by definition, a wellformed
type
. Each wellformed expression has, by definition, a
value
. Given an expression for evaluation,

• GHCi checks that the expression is
  syntactically
  correct, that is, it conforms to the rules of syntax laid down by Haskell.
  
• If it is, GHCi infers a type for the expression, or checks that the type supplied by the programmer is correct.
  
• Provided the expression is well-typed, GHCi evaluates the expression by reducing it to its simplest possible form to produce a value. Provided the value is printable, GHCi then prints it at the terminal.
  

In this chapter we continue the study of Haskell by taking a closer look at these processes.

One way of finding out whether or not an expression is wellformed is of course to use GHCi. There is a command
:type expr
which, provided
expr
is wellformed, will return its type. Here is a session with GHCi (with some of GHCi’s responses abbreviated):
ghci> 3 +4)

:1:5: parse error on input `)'

GHCi is complaining that on line 1 the character
')'
at position 5 is unexpected; in other words, the expression is not syntactically correct.

ghci> :type 3+4

3+4 :: Num a => a

GHCi is asserting that the type of
3+4
is a number. More on this below.

ghci> :type if 1==0 then 'a' else "a"

:1:23:

Couldn't match expected type `Char' with actual type `[Char]'

In the expression: "a"

In the expression: if 1 == 0 then 'a' else "a"

GHCi expects the types of
expr1
and
expr2
in a conditional expression
if test then expr1 else expr2

to be the same. But a character is not a list of characters so the conditional expression, though conforming to the rules of Haskell syntax, is not wellformed.

ghci> sin sin 0.5

:1:1:

No instance for (Floating (a0 -> a0))

arising from a use of `sin'

Possible fix: add an instance declaration for

(Floating (a0 -> a0))

In the expression: sin sin 0.5

In an equation for `it': it = sin sin 0.5

GHCi gives a rather opaque error message, complaining that the expression is not wellformed.

ghci> sin (sin 0.5)

0.4612695550331807

Ah, GHCi is happy with this one.

ghci> :type map

map :: (a -> b) -> [a] -> [b]

GHCi returns the type of the function
map
.

ghci> map

:1:1:

No instance for (Show ((a0 -> b0) -> [a0] -> [b0]))

arising from a use of `print'

Possible fix:

add an instance declaration for

(Show ((a0 -> b0) -> [a0] -> [b0]))

In a stmt of an interactive GHCi command: print it

GHCi is saying that it doesn’t know how to print a function.

ghci> :type 1 `div` 0

1 `div` 0 :: Integral a => a

GHCi is asserting that the type of
1 `div` 0
is an integral number. The expression
1 `div` 0
is therefore wellformed and possesses a value.

ghci> 1 `div` 0

*** Exception: divide by zero

GHCi returns an error message. So what is the value of
1 `div` 0
? The answer is that it is a special value, written mathematically as ⊥ and pronounced ‘bottom’. In fact, Haskell provides a predeclared name for this value, except that it is called
undefined
, not bottom.

ghci> :type undefined

undefined :: a

ghci> undefined

*** Exception: Prelude.undefined

Haskell is not expected to produce the value ⊥. It may return with an error message, or remain perpetually silent, computing an infinite loop, until we interrupt the computation. It may even cause GHCi to crash. Oh, yes.

ghci> x*x where x = 3

:1:5: parse error on input `where'

ghci> let x = 3 in x*x

9

A
where
clause does
not
qualify an expression in Haskell, but the whole of the right-hand side of a definition. Thus the first example is not a wellformed expression. On the other hand, a
let
expression
let in

is wellformed, at least assuming the definitions in

are and the expression

is. Let-expressions appear infrequently in what follows, but occasionally they can be useful.

As we have seen, a script is a collection of names and their definitions. Names for functions and values begin with a lowercase letter, except for data constructors (see later on) which begin with an uppercase letter. Types (e.g.
Int
), type classes (e.g.
Num
) and modules (e.g.
Prelude
or
Data.Char
) also begin with an uppercase letter.

An operator is a special kind of function name that appears between its (two) arguments, such as the
+
in
x + y
or the
++
in
xs ++ ys
. Operator names begin with a symbol. Any (non-symbolic) function of two arguments can be converted into an operator by enclosing it in back quotes, and any operator can be converted to a prefix name by enclosing it in parentheses. For example,

Operators have different levels of precedence (binding power). For example,

If in any doubt, add parentheses to remove possible ambiguity. By the way, we can use any names we like for lists, including
x
,
y
,
goodylist
, and so on. But a simple aid to memory is to use
x
for things,
xs
for lists of things, and
xss
for lists of lists of things. That explains why we wrote
yss
in the expression
yss !! 3
in the last line above.

Operators with the same level of precedence normally have an order of association, either to the left or right. For example, the usual arithmetic operators associate to the left:

3 - 4 - 2
means
(3 - 4) - 2

3 - 4 + 2
means
(3 - 4) + 2

3 / 4 * 5
means
(3 / 4) * 5

Functional application, which has higher precedence than any other operator, also associates to the left:

Some operators associate to the right:

Of course, if an operator, such as functional composition, is associative the order has no effect on meaning (i.e. the value is the same). Again, one can always add parentheses to remove possible ambiguity.

We can declare new operators; for example:

The conditional expression has low binding power, so the expression above means

if even x then y else (x + y)

not
(if even x then y else x) + y
. Again, one can always use parentheses to group differently.