Thinking Functionally with Haskell (42 page)

bfs ps [] mqs = bfs ps mqs []

bfs ps ((ms,p):mps) mqs

| solved p
= Just (reverse ms)

| p `elem` ps = bfs ps mps mqs

| otherwise
= bfs (p:ps) mps (succs (ms,p) ++ mqs)

The additional argument is a temporary frontier used to store successors. When the first frontier is exhausted the contents of the temporary frontier are installed as the new frontier. Adding successors to the front of the temporary frontier takes time proportional to the number of successors, not to the size of the frontier, and that leads to a faster algorithm. On the other hand, the new version of
bfs
is not the same as the old one because successive frontiers are traversed alternately from left to right and from right to left. Nevertheless a shortest solution will still be found if one exists.

The second source of inefficiency is the membership test. Use of a list to store previously explored positions is slow because the membership test can take time proportional to the number of currently explored positions. It would all be easier if positions were integers in the range [0 ..
n
−1] for some
n
, for then we could use a boolean array with bounds (0,
n
−1) to tick off positions as they arise. The membership test would then consist of a single array lookup.

One can imagine coding positions as integers, but not as integers in an initial segment of the natural numbers. For instance, a Sudoku position (see
Chapter 5
) can be expressed as an integer consisting of 81 digits. So suppose we have a function
encode :: Position -> Integer

that encodes positions as integers. To reduce the range we can define

for some suitable
n :: Int
. The result of
hash
is then an integer in the range
[0..n-1]
.

The one hitch, and it’s a big one, is that two distinct positions may hash to the
same integer. To solve this problem we abandon the idea of having an array of booleans, and instead have an array of lists of positions. The positions in the array at index
k
are all those whose hash value is
k
. There is no guarantee that any of this will improve efficiency in the worst case, but if we allow
n
to be reasonably large, and trust that the hash function assigns integers to positions in a reasonably evenly distributed way, then the complexity of a membership test is reduced by a factor of
n
.

With this hashing scheme the revised code for
solve
is:

We cannot leave the subject of arrays without mentioning a very nice Haskell library
Data.Array
that provides purely functional operations on immutable arrays. The operations are implemented using mutable arrays, but the interface is purely functional.

The type
Array i e
is an abstract type of arrays with indices of type
i
and elements of type
e
. One basic operation for constructing arrays is
array :: Ix i => (i,i) -> [(i,e)] -> Array i e

This function take a pair of bounds, the lowest and highest indices in the array, and a list of index-element pairs specifying the array entries. The result is an array with the given bounds and entries. Any entry missing from the association list is deemed to be the undefined entry. If two entries have the same index, or one of the indices is out of bounds, the undefined array is returned. Because of these checks, array construction is strict in the indices, though lazy in the elements. Building the array takes linear time in the number of entries.

A simple variant of
array
is
listArray
which takes just a list of elements:

listArray :: Ix i => (i,i) -> [e] -> Array i e

listArray (l,r) xs = array (l,r) (zip [l..r] xs)

Finally, there is another way of building arrays called
accumArray
whose type appears rather daunting:
Ix i => (e -> v -> e) -> e -> (i,i) -> [(i,v)] -> Array i e
The first argument is an ‘accumulating’ function for transforming array entries and new values into new entries. The second argument is an initial entry for each index. The third argument is a pair of bounds, and the fourth and final argument is an association list of index–value pairs. The result is an array built by processing the association list from left to right, combining entries and values into new entries using the accumulating function. The process takes linear time in the length of the association list, assuming the accumulating function takes constant time.

That’s what
accumArray
does in words. In symbols,

elems (accumArray f e (l,r) ivs)

= [foldl f e [v | (i,v) <- ivs, i==j] | j <- [l..r]]

where
elems
returns the list of elements of an array in index order. Well, the identity above is not quite true: there is an additional restriction on
ivs
, namely that every index should lie in the specified range. If this condition is not met, then the left-hand side returns an error while the right-hand side does not.

Complicated as
accumArray
seems, it turns out to be a very useful tool for solving certain kinds of problem. Here are two examples. First, consider the problem of representing directed graphs. Directed graphs are usually described in mathematics in terms of a set of
vertices
and a set of
edges
. An edge is an ordered pair (
j
,
k
) of vertices signifying that the edge is directed from
j
to
k
. We say that
k
is
adjacent
to
j
. We will suppose that vertices are named by integers in the range 1 to
n
for some
n
. Thus
type Vertex = Int

type Edge
= (Vertex,Vertex)
type Graph
= ([Vertex],[Edge])

vertices g = fst g

edges g
= snd g

In computing, directed graphs are often described in terms of adjacency lists:

The problem with this definition of
adjs
is that it takes time proportional to the number of edges to compute the adjacency list of any particular vertex. Better is to implement
adjs
as an array:
adjArray :: Graph -> Array Vertex [Vertex]

Then we have

adjs g v = (adjArray g)!v

where
(!)
denotes the operation of array-indexing. For reasonably sized arrays this operation takes constant time.

The specification of
adjArray
is that

elems (adjArray g)

= [[k | (j,k) <- edges g, j==v] | v <- vertices g]

Using this specification we can calculate a direct definition of
adjArray
. To keep each line short, abbreviate
edges g
to
es
and
vertices g
to
vs
, so
elems (adjArray g) = [[k | (j,k) <- es, j==v] | v <- vs]

Concentrating on the right-hand side, the first step is to rewrite it using the law
foldr (:) [] = id
. That gives the expression
[foldr (:) [] [k | (j,k) <- es, j==v] | v <- vs]

Next we use the law
foldr f e xs = foldl (flip f) e (reverse xs)
for all finite lists
xs
. Abbreviating
flip (:)
to
(@)
, we obtain
[foldl (@) [] (reverse [k | (j,k) <- es, j==v]) | v <- vs]

Distributing
reverse
we obtain the expression

[foldl (@) [] [k | (j,k) <- reverse es, j==v] | v <- vs]

Next we use
swap (j,k) = (k,j)
to obtain

[foldl (@) [] [j | (k,j) <- es', j==v] | v <- vs]

where
es' = map swap (reverse es)
. Finally, using
n = length vs
and the specification of
accumArray
, we obtain

elems (adjArray g)

= elems (accumArray (flip (:)) [] (1,n) es')

That means we can define

adjArray g = accumArray (flip (:)) [] (1,n) es

where n = length (vertices g)

es = map swap (reverse (edges g))

This definition of
adjArray g
computes the successors in time proportional to the number of edges.

Here is the second example of the use of
accumArray
. Suppose we are given a list of
n
integers, all in the range (0,
m
) for some
m
. We can sort this list in Θ(
m
+
n
) steps by counting the number of times each element occurs:

count :: [Int] -> Array Int Int

count xs = accumArray (+) 0 (0,m) (zip xs (repeat 1))

The value
repeat 1
is an infinite list of
1
s. Counting takes Θ(
n
) steps. Having counted the elements, we can now sort them:
sort xs = concat [replicate c x

| (x,c) <- assocs (count xa)]

The function
assocs
is yet another library function and returns the list of index– element pairs of an array in index order. The sorting is completed in Θ(
m
) steps.

As well as the above operations
Data.Array
contains one or two more, including the update operation
(//)
:
(//) :: Ix i => Array i e -> [(i,e)] -> Array i e

For example, if
xa
is an
n
×
n
matrix, then

xa // [((i,i),0) | i <- [1..n]]

is the same matrix except with zeros along the diagonal. The downside of
(//)
is that it takes time proportional to the size of the array, even for an update involving a single element. The reason is that a completely new array has to be constructed because the old array
xa
continues to exist.

We have ended the chapter back in the world of pure functional programming,
where equational reasoning can be used both to calculate definitions and to optimise them. Although the monadic style is attractive to programmers who are used to imperative programming, there remains the problem of how to reason about monadic programs. True, equational reasoning is still possible in certain situtations (see Exercise F for an example), but it is not so widely applicable as it is in the pure functional world (witness the correctness of the partition phase of Quicksort). Imperative programmers have the same problem, which they solve (if they bother to) by using predicate calculus, preconditions, postconditions and loop invariants. How to reason directly with monadic code is still a topic of ongoing research.

Our best advice is to use the monadic style sparingly and only when it is really useful; otherwise the most important aspect of functional programming, the ability to reason mathematically about its constructs, is lost.

Exercise A

Recall that

putStr = foldr (>>) done . map putChar

What does

foldl (>>) done . map putChar

do? Justify your answer by expressing
(>>)
in terms of
(>>=)
and appealing to the monad laws.

Exercise B

Using a pattern-matching style, define a function

add3 :: Maybe Int -> Maybe Int -> Maybe Int -> Maybe Int

that adds three numbers, provided all of them exist. Now rewrite
add3
using the
Maybe
monad.

Exercise C

The monadic definition of
cp
in
Section 10.1
is still inefficient. We might prefer to write
cp (xs:xss) = do {ys <- cp xss;

x <- xs;

return (x:ys)}

By definition a
commutative
monad is one in which the equation

holds. The
IO
monad is certainly not commutative, while some other monads are. Is the
Maybe
monad commutative?

Exercise D

Every monad is a functor. Complete the definition

Currently Haskell does not insist that the
Monad
class should be a subclass of
Functor
, though there are plans to change this in future releases. Instead, Haskell provides a function
liftM
equivalent to
fmap
for monads. Give a definition of
liftM
in terms of
return
and
>>=
.