Thinking Functionally with Haskell (15 page)

The answer to the tricky question is: no. Either argument
n
or argument
xs
has to be examined and, whichever happens first, ⊥ is the result if ⊥ is the value of thaargument.

All four equations are valid for all lists
xs
and for all
m
,
n
≠⊥, under either definition.

The function
splitAt n
can be defined by

Answer to Exercise I

I would agree with (3), (4), (5) and (7).

Answer to Exercise J

The only false equation is
map f . sort = sort . map f
which is true only i
f
is order-preserving,
i.e.
x
≤
y
≡
f x
≤
f y
.

Answer to Exercise K

The calculation is

We seem to be stuck, as no law applies. Try the right-hand side:
unzip . map (cross (f,g))

=
{definition of
unzip
}

fork (map fst, map snd) . map (cross (f,g))

=
{law of
fork
}

fork (map fst . map (cross (f,g)),

map snd . map (cross (f,g)))

=
{law of
map
}

fork (map (fst . cross (f,g)),

map (snd . cross (f,g)))

=
{laws of
fst
and
snd
}

fork (map (f . fst), map (g . snd))

Phew. Both sides have reduced to the same expression. That is often the way with calculations: one side doesn’t always lead easily to the other, but both sides reduce to the same result.

The calculations we have seen so far have all been carried out at the function level. Such a style of definition and proof is called
point-free
(and also
pointless
by some jokers). Point-free proofs are what the automatic calculator of
Chapter 12
produces. The point-free style is very slick, but it does necessitate the use of various
plumbing combinators
, such as
fork
and
cross
, to pass arguments to functions. Plumbing combinators push values around, duplicate them and even eliminate them. As an example of the last kind,
const :: a -> b -> a

const x y = x

This little combinator is in the standard prelude and can be quite useful on occasion.

Two more plumbing combinators, also defined in the standard prelude, are
curry
and
uncurry
:
curry :: ((a, b) -> c) -> a -> b -> c

curry f x y = f (x,y)

uncurry :: (a -> b -> c) -> (a,b) -> c

uncurry f (x,y) = f x y

A
curried
function is a function that takes its arguments one at a time, while a non-curried function takes a single, tupled argument. The key advantage of curried
functions is that they can be
partially applied
. For instance,
take n
is a perfectly valid function in its own right, and so is
map f
. That is why we have used curried functions from the start.

By the way, curried functions are named after Haskell B. Curry, an American logician. And, yes, that is where Haskell got its name.

Answer to Exercise L

We have
cross = uncurry bimap
, where
uncurry
was defined in the previous answer.

Here is the instance of
Either
:

Most of the functions introduced in this chapter can be found in the Haskell standard prelude. Functors, bifunctors, and natural transformations are explained in books about Category Theory. Two such are
Basic Category Theory for Computer Scientists
(MIT Press, 1991) by Benjamin Pierce, and
The Algebra of Programming
(Prentice Hall, 1997) by Richard Bird and Oege de Moor.

Also on the subject of laws, read Phil Wadler’s influential article
Theorems for free!
which can be found at
homepages.inf.ed.ac.uk/wadler/papers/free/

In mathematics, the so-called taxicab number taxicab(
n
) is the smallest number that can be expressed as the sum of two positive cubes in
n
distinct ways. So 1729 = taxicab(2). Google ‘taxicab numbers’ for more information.

H
OW TO PLAY
: Fill in the grid so that every row,
every column and every 3 × 3 box contains the
digits 1–9. There’s no maths involved. You
solve the puzzle with reasoning and logic.
Advice on how to play Sudoku, the
Independent This chapter is devoted to an extended exercise in the use of lists to solve problems, and in the use of equational reasoning to reason about them and to improve efficiency.

The game of Sudoku is played on a 9 by 9 grid, though other sizes are also possible. Given a matrix, such as that in
Figure 5.1
, the idea is to fill in the empty cells with the digits 1 to 9 so that each row, column and 3×3 box contains the numbers 1 to 9. In general there may be any number of solutions, though in a good Sudoku puzzle there should always be a unique solution. Our aim is to construct a program to solve Sudoku puzzles. Specifically, we will define a function
solve
for computing a list of all the ways a given grid may be completed. If only one solution is wanted, then we can take the head of the list. Lazy evaluation means that only the first result will then be computed.

We begin with a specification, then use equational reasoning to calculate a more efficient version. There’s no maths involved, just reasoning and logic!

Here are the basic data types of interest, starting with matrices:

type Matrix a = [Row a]

type Row a = [a]

The two type synonyms say nothing more than that
Matrix a
is a synonym for
[[a]]
. But the way it is said emphasises that a matrix is a list of
rows
; more precisely, a
m
×
n
matrix is a list of
m
rows in which each row is a list with the same length
n
. Haskell type synonyms cannot enforce such constraints, though there are languages, called
dependently-typed
languages, that can.

A grid is a 9 × 9 matrix of digits:

The valid digits are 1 to 9 with 0 standing for a blank:

Recall that
Char
is also an instance of the type class
Enum
, so
['1' .. '9']
is a valid expression and does indeed return the list of nonzero digits.

We will suppose for simplicity that the input grid contains only digits and blanks, so we do not have to check for the input being well-formed. But should we also insist that no non-blank digit is repeated in any row, column or box? If there were such repetitions there would be no solution. We postpone this decision until after we see how the rest of the algorithm pans out.

Now for the specification. The aim is to write down the simplest and clearest specification without regard to how efficient the result might be. That’s a key difference between functional programming and other forms of program construction: we can always begin with a clear and simple, though possibly extremely inefficient definition of
solve
, and then use the laws of functional programming to massage the computation into one that takes acceptable time and space.

One possibility is first to construct a list of all possible correctly filled grids, a vastly long but still finite list, and then to test the given grid against each of them to identify those whose entries match the given non-blank ones. Certainly that approach takes the idea of an inefficient specification to the extreme. Another reasonable alternative is to start with the given grid and to complete it by filling in every possible choice for the blank entries. The result will be a list of filled grids. Then we can filter this list for those that don’t contain duplicates in any row, box or column. This specification is implemented by

solve :: Grid -> [Grid]

solve = filter valid . completions

where the subsidiary functions have types

Let us work on
completions
first and consider
valid
afterwards. One way of defining
completions
is by a two-step process:
completions = expand . choices

where

The function
choices
installs the available digits for each cell:
choices
= map (map choice)

choice d = if blank d then digits else [d]

If the cell is blank, then all digits are installed as possible choices; otherwise there is only one choice and a singleton is returned. If we want to apply
f
to every element of a matrix, then
map (map f)
is the function to use because, after all, a matrix is just a list of lists.

After applying
choices
we obtain a matrix each of whose entries is a list of digits. What we want to do next is to define
expand
to convert this matrix into a list of
grids by installing all the choices in all possible ways. That seems a little difficult to think about, so let’s consider a simpler problem first, namely when instead of a 9 × 9 matrix we have a list of length 3. Suppose we want to convert
[[1,2,3],[2],[1,3]]

into the list

[[1,2,1],[1,2,3],[2,2,1],[2,2,3],[3,2,1],[3,2,3]]

The second list of lists arises by taking, in all possible ways, one element from the first list, one element from the second list and one element from the third list. Let us call the function that does this
cp
(short for ‘cartesian product’, which is exactly what a mathematician would call it). There doesn’t seem to be any clever way of computing
cp
in terms of other functions, so we adopt the default strategy of defining this function by breaking up its argument list into two possibilities, the empty list
[]
and a nonempty list
xs:xss
. You might guess the definition of
cp []
but you would probably be wrong; the better alternative is to think about the second case first. Suppose we assume
cp [[2],[1,3]] = [[2,1],[2,3]]

How can we extend this definition to one for
cp ([1,2,3]:[[2],[1,3]])
? The answer is to prefix
1
to every element of
cp [[2],[1,3]]
, then to prefix
2
to every element of the same list, and finally to prefix
3
to every element. That process can be expressed neatly using a list comprehension:
cp (xs:xss) = [x:ys | x <- xs, ys <- cp xss]

In words, prefix every element of
xs
to every element of
cp xss
in all possible ways.