Thinking Functionally with Haskell (47 page)

Why are the first and second definitions of
int
given in the text inefficient, compared to the third definition?

Exercise I

Is
"(3)"
a fully parenthesised expression? Is it a non-fully parenthesised expression? Haskell allows parenthesised constants:
ghci> (3)+4

7

Design a parser for fully parenthesised expressions that allows parentheses around constants.

Exercise J

Consider the grammar
expr ::= term {op term}*
. Define
pair
and
shunt
so that the following parser is legitimate:
expr = do {e1 <- term;

pes <- many (pair op term);

return (foldl shunt e1 pes)}

Exercise K

Define the parsers
addop
and
mulop
.

Exercise L

Consider again the showing of expressions with all four arithmetic operations. The rules for putting in parentheses come down to: we need parentheses around
e1
in
e1 op e2
if
op
is a multiplication operator, and the root of
e1
isn’t. Dually we will need parentheses around
e2
if either
op
is a multiplication operator or the root of
e2
isn’t. Defining
isMulOp Mul = True

isMulOp Div = True

isMulOp _
= False

construct an alternative definition of
show
involving a subsidiary function
showsF :: (Op -> Bool) -> Expr -> ShowS

Answer to Exercise A

Because
(==)
is the equality test on floating-point numbers, and different numbers cannot be equal.

instance Eq Angle where

Angle x == Angle y = reduce x == reduce y

where

reduce x | x<0 = reduce (x + r)

| x>r = reduce (x - r)

| otherwise = x

where r = 2*pi

Answer to Exercise B

instance Monad Parser where

return x = Parser (\s -> Just (x,s))

P >>= q = Parser (\s -> case apply p s of

Nothing -> apply q s

Just (x,s') -> Just (x,s'))

Answer to Exercise C

fail >> p

= fail >>= const p

= fail

The fact that
fail >>= p = fail
is immediate from the definition of
fail
and the definition of
p >>= q
.

Answer to Exercise D

Yes, but the result is only a deterministic parser when either
p
or
q
is
fail
. The function
limit
can be defined by
limit p = Parser (take 1 . apply p)

Answer to Exercise E

mzero = fail

mplus = (<|>)

Answer to Exercise F

Yes, both the list monad and the
Maybe
monad satisfy the five laws. For example, in the list monad
mzero >>= f = concat (map f []) = [] = mzero

xs >> mzero = concat (map (const []) xs) = [] = mzero
With
Maybe
the left-distribution law doesn’t hold. We have
(Just x `mplus` q) >>= (\x -> Nothing)

= Just x >>= (\x -> Nothing)

= Nothing

but

(Just x >> \x -> Nothing) `mplus`

(q >>= \x -> Nothing)

= Nothing `mplus` (q >>= \x -> Nothing)

= q >>= \x -> Nothing

The two resulting expressions are not equal (take
q = undefined
).

Answer to Exercise G

float :: Parser Float

float = do {ds <- some digit;

char '.';

fs <- some digit;

return (foldl shiftl 0 ds +

foldr shiftr 0 fs)}

where shiftl n d = 10*n + fromIntegral d

shiftr f x = (fromIntegral f+x)/10

The parser
digit
returns an
Int
, which has to be converted to a number (in this case a
Float
).

Answer to Exercise H

White space is parsed twice. For example, calling the first version
int1
and the third
int3
we have
ghci> apply int3 $ replicate 100000 ' ' ++ "3"

[(3,"")]

(1.40 secs, 216871916 bytes)

ghci> apply int1 $ replicate 100000 ' ' ++ "3"

[(3,"")]

(2.68 secs, 427751932 bytes)

Answer to Exercise I

No, according to the first grammar for
expr
, only binary expressions can be parenthesised. Yes, according to the second grammar as arbitrary expressions can be parenthesised.

The revised grammar is

expr ::= term | '(' expr op expr ')'

term ::= nat | '(' expr ')'

The corresponding parser is

expr = token (term <|> paren binary)
where

term = token (constant <|> paren expr)

binary = do {e1 <- expr;

p <- op;

e2 <- expr;

return (Bin p e1 e2)}

Answer to Exercise J

pair :: Parser a -> Parser b -> Parser (a,b)

pair p q = do {x <- p; y <- q; return (x,y)}

shunt e1 (p,e2) = Bin p e1 e2

Answer to Exercise K

addop = (symbol "+" >> return Plus) <|>

(symbol "-" >> return Minus)

mulop = (symbol "*" >> return Mul) <|>

(symbol "/" >> return Div)

Answer to Exercise L

show e = showsF (const False) e ""

where

showsF f (Con n) = showString (show n)

showsF f (Bin op e1 e2)

= showParen (f op) (showsF f1 e1 . showSpace .

showsop op . showSpace . showsF f2 e2)

where f1 x = isMulOp op && not (isMulOp x)

f2 x = isMulOp op || not (isMulOp x)

The design of functional parsers in a monadic setting has long been a favourite application of functional programming. Our presentation follows that of ‘Monadic parsing in Haskell’ by Graham Hutton and Erik Meijer, which appears in
The Journal of Functional Programming
8(4), 437–144, 1998.

This final chapter is devoted to a single programming project, the design and implementation of a simple calculator for carrying out point-free equational proofs. Although the calculator provides only a small subset of the facilities one might want in an automatic proof assistant, and is highly restrictive in a number of other ways, it will nevertheless be powerful enough to prove many of the point-free laws described in previous chapters – well, provided we are prepared to give it a nudge in the right direction if necessary. The project is also a case study in the use of modules. Each component of the calculator, its associated types and functions, is defined in an appropriate module and linked to other modules through explicit import and export lists.

The basic idea is to construct a single function
calculate
with type
calculate :: [Law] -> Expr -> Calculation

The first argument of
calculate
is a list of laws that may be applied. Each law consists of a descriptive name and an equation. The second argument is an expression and the result is a calculation. A calculation consists of a starting expression and a sequence of steps. Each step consists of the name of a law and the expression that results by applying the left-hand side of the law to the current expression. The calculation ends when no more laws can be applied, and the final expression is the conclusion. The entire process is automatic, requiring no intervention on the part of the user.

Laws, expressions and calculations are each elements of appropriate data types to be defined in the following sections. But for now let us plunge straight in with an example to show the framework we have in mind.

Here are some laws (we use a smaller font to avoid breaking lines):

definition filter: filter p = concat . map (box p)

definition box: box p = if p one nil

if after dot: if p f g . h = if (p . h) (f . h) (g . h)

dot after if: h . if p f g = if p (h . f) (h . g)

nil constant: nil . f = nil

map after nil: map f . nil = nil

map after one: map f . one = one . f

map after concat: map f . concat = concat . map (map f)

map functor: map f . map g = map (f . g)

map functor: map id = id

Each law consists of a name and an equation. The name of the law is terminated by a colon sign, and an equation consists of two expressions separated by an equals sign. Each expression describes a function; our calculator will be one that simplifies functional expressions only (yes, it’s a pointless calculator). Expressions are built from constants, like
one
and
map
, and variables, like
f
and
g
. The precise syntax will be given in due course. Note that there are no conditional laws, equations that are valid only if some subsidiary conditions are met. That will limit what we can do with the calculator, but it still leaves enough to be interesting.

Suppose we want to simplify the expression
filter p . map f
. Here is one possible calculation:
filter p . map f

=
{definition filter}

concat . map (box p) . map f

=
{map functor}

concat . map (box p . f)

=
{definition box}

concat . map (if p one nil . f)

=
{if after dot}

concat . map (if (p . f) (one . f) (nil . f))

=
{nil constant}

concat . map (if (p . f) (one . f) nil)

The steps of the calculation are displayed in the conventional format with the name of the law being invoked printed in braces between the two expressions to which
it applies. No more laws apply to the final expression, so that is the result of the calculation. It is certainly not simpler than the expression we started out with.

The calculator could have applied some of the laws in a different order; for example, the definition of
box
could have been applied at the second step rather than at the third. But the conclusion would have been the same. It is also possible, though not with this particular set of laws, that an expression could be simplified to different conclusions by different calculations. However, at the outset we make the decision that
calculate
returns just one calculation, not a tree of possible calculations.

Notice what is happening at each step. Some left-hand side of some law is
matched
against some subexpression of the current expression. If a match is successful the result is a
substitution
for the variables occurring in the law. For example, in the second step, the subexpression
map (box p) . map f
is successfully matched with the first map functor law, resulting in a substitution in which the variable
f
of the functor law is bound to the expression
box p
, and the variable
g
is bound to
f
. The result of the step involves
rewriting
the subexpression with the corresponding instance of the right-hand side of the law in which each variable is replaced by its binding expression. Matching, substitutions and rewriting are all fundamental components of the calculator.

Now suppose that with the same set of laws as above we want to simplify the expression
map f . filter (p . f)
. Here is the calculation:
map f . filter (p . f)

=
{definition filter}

map f . concat . map (box (p . f))

=
{map after concat}

concat . map (map f) . map (box (p . f))

=
{map functor}

concat . map (map f . box (p . f))

=
{definition box}

concat . map (map f . if (p . f) one nil)

=
{dot after if}

concat . map (if (p . f) (map f . one) (map f . nil))

=
{map after nil}

concat . map (if (p . f) (map f . one) nil)

=
{map after one}

concat . map (if (p . f) (one . f) nil)

Again, some of the laws could have been applied in a different order. No more laws apply to the final expression so that is the result of the calculation.

The point about these two calculations is that the two final expressions are the same, so we have proved
filter p . map f = map f . filter (p . f)

This is the way we will conduct equational proofs, simplifying both sides to the same conclusion. Rather than show two calculations, one after the other, the two results can be
pasted
together by recording the first calculation and then appending the steps of the second calculation in reverse. The main advantage of this scheme is simplicity; we do not have to invent a new format for proofs, and we do not have to apply laws from right to left in order to reach the desired goal. Accordingly, we will also define a function
prove :: [Law] -> Equation -> Calculation