Thinking Functionally with Haskell (37 page)

main
= interact replace

replace = unlines . map cleanup . filter code . lines

code xs = null xs || head xs == '>'

cleanup xs = if null xs then [] else tail xs

The program is the computation associated with the identifier
main
, and there always has to be a definition associated with this name if we want to compile a program. The function
lines
splits a text into lines, and
unlines
reassembles the text by putting a single newline between lines. If we store the program in
lhs2hs.lhs
, we can compile it and then run it:
$ ghc lhs2hs.lhs

$ lhs2hs myscript.hs

In the second line, the input is taken from
myscript.lhs
and the output is directed to
myscript.hs
.

Stream-based interaction was the main method for interacting with the outside world in early versions of Haskell. However, the model presented above is too simple for most practical purposes. In a serious application one wants to do other things than reading and printing characters to a screen. For example, one also wants to open and read files, to write to or delete files, and in general to interact with all the mechanisms that are available in the world outside the confines of a functional programming language. Interaction takes place in time, and the order in which events occur has to be managed correctly by the programmer. In the stream-based approach, this ordering of events is represented by the order of the elements in a list; in other words, it is represented in the data and not reflected primarily in the way the program is composed. In the following chapter we will consider another approach to interaction, indeed, a general method for writing programs that have to control an orderly sequence of events. In this approach, the order is made explicit in the way the program is composed.

We end with another application of cyclic lists. Imagine reading a book consisting of a nonempty list of pages. To navigate around the book we need some way of moving on to the next page and moving back to the previous page. Other navigation tools would be useful, but we’ll stick with these two. Here is an interactive session with a particularly boring book
book
consisting of three pages:
ghci> start book

"Page 1"

ghci> next it

"Page 2"

ghci> prev it

"Page 1"

ghci> next it

"Page 2"

ghci> next it

"Page 3"

In GHCi the variable
it
is bound to the expression just typed at the prompt. We started a book and what was printed was the first page. We turned to the next page, and then returned to the previous one. The interesting question is what should happen when we turn to the next page after the last one. Should the navigation report an error, just deliver the last page again or go to the first page? Suppose we decide on the last alternative, namely that the next page after the last one should be the first page, and the previous page before the first one should be the last page. In other words, our book is an instance of a
cyclic doubly-linked list
.

Here is the relevant datatype declaration:

We print a doubly-linked list by displaying the current entry:

Our book is then a list
[p1,p2,p3]
of three pages, where

This example suggests that the function
mkCDList :: [a] -> DList a
for converting a (nonempty) list
as
into a doubly-linked list can be specified as the first element in a finite list
xs
of doubly-linked lists satisfying the following three properties:

map elem xs = as

map prev xs = rotr xs

map next xs = rotl xs

Here,
rotr
and
rotl
(short for
rotate right
and
rotate left
), are defined by

rotr xs = [last xs] ++ init xs

rotl xs = tail xs ++ [head xs]

Observe now that for any list
xs
of doubly-linked lists we have

xs = zipWith3 Cons

(map elem xs) (map prev xs) (map next xs)

where
zipWith3
is like
zipWith
except that it takes three lists instead of two. The standard prelude definition is:

zipWith3 f (x:xs) (y:ys) (z:zs)

= f x y z : zipWith3 f xs ys zs

zipWith3
= []

We will see another definition in a moment. We can prove the claim above by induction. It clearly holds for the undefined and empty lists. For the inductive case we reason:

x:xs

=
{since
xs
is a doubly-linked list}

Cons (elem x) (prev x) (next x):xs

=
{induction}

Cons (elem x) (prev x) (next x):

(zipWith3 Cons

(map elem xs) (map prev xs) (map next xs))

=
{definition of
zipWith3
and
map
}

zipWith3 Cons

(map elem (x:xs)) (map prev (x:xs)) (map next (x:xs)

Putting this result together with our specification of doubly-linked lists, we arrive at

This definition involves a cyclic list
xs
. Does it work? The answer is: No, it doesn’t. The reason is that
zipWith3
as defined above is too eager. We need to make it lazier by not demanding the values of the second two lists until they are really needed:

zipWith3 f (x:xs) ys zs

= f x (head ys) (head zs):

zipWith3 f xs (tail ys) (tail zs)

zipWith3
= []

An equivalent way to define this function is to make use of Haskell’s
irrefutable patterns
:

zipWith3 f (x:xs)
(y:ys)
(z:zs)

= f x y z : zipWith3 f xs ys zs

zipWith3
= []

An irrefutable pattern is introduced using a tilde, and
~(x:xs)
is matched lazily, meaning that no matching is actually performed until either
x
or
xs
is needed. Just to convince ourselves that the above definition of
mkCDList
with the revised definition of
zipWith3
does make progress, let
xs
₀
=⊥ and
xs
_n
+1
= zipWith3 Cons "A" (rotr xs
_n
) (rotl xs
_n
)
Then
xs
₁
is given by

and
xs
²
by

and so on.

Exercise A

Given three lists
xs
,
ys
and
zs
in strictly increasing order, we have
merge (merge xs ys) zs} = merge xs (merge ys zs)

Thus
merge
is associative. Assuming in addition that the first elements of
xs
,
ys
and
zs
are in strictly increasing order, we also have
xmerge (xmerge xs ys) zs = xmerge xs (xmerge ys zs)

Does it follow that in the expression
foldr1 xmerge multiples
we could replace
foldr1
by
foldl1
?

Exercise B

The standard prelude function
cycle :: [a] -> [a]
takes a list
xs
and returns a list consisting of an infinite number of repetitions of the elements of
xs
. If
xs
is the empty list, then
cycle []
returns an error message. For instance
cycle "hallo" = "hallohallohallo...

Define
cycle
using a cyclic list. Ensure that your definition works on empty, finite and infinite lists.

Exercise C

The fibonacci function is defined by

Write down a one-line definition of the list
fibs
that produces the infinite list of Fibonacci numbers.

Exercise D

A well-known problem, due to the mathematician W.R. Hamming, is to write a program that produces an infinite list of numbers with the following properties: (i) the list is in strictly increasing order; (ii) the list begins with the number 1; (iii) if the list contains the number
x
, then it also contains the numbers 2
x
, 3
x
and 5
x
; (iv) the list contains no other numbers. Thus, the required list begins with the numbers 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, . . .

Write a definition of
hamming
that produces this list.

Exercise E

Prove that
approx n xs
⊑
xs
for all
n
. Now prove that if
approx n xs
⊑
ys
for all
n
, then
xs
⊑
ys
. Hence conclude that

Exercise F

Give a counter-example to the claim that
xs=ys
if
xs!!n=ys!!n
for all
n
.

Exercise G

Prove that
iterate f x = x: map f (iterate f x)
.

Exercise H

In the definition of
primes
as a cyclic list, could we have defined
mergeAll = foldr xmerge []

as an alternative to the definition in the text?

Exercise I

Recall that

Given that
prs n=
p
₁
:
p
²
: · · ·
p
_n
:⊥, where
p
_j
is the
j
th prime, sketch how to show that
crs n=
c
₁
:
c
²
: · · ·
c
_m
:⊥, where
c
_j
is the
j
th composite number (so
c
₁
=
4) and Hence show that
primes
does produce the infinite list of primes. We said in the text that it is not the case that the
n
th approximation
primes
_n
of
primes
is equal to
approx n primes
. In fact