Thinking Functionally with Haskell (36 page)

determines the total score after playing a given number of rounds.

The instructive aspect of the game is how to represent strategies. We are going to consider two ways, calling them
Strategy1
and
Strategy2
. The obvious idea is to take
type Strategy1 = [Move] -> Move

Here, a strategy is a function which takes the (finite) list of moves made by the opponent so far and returns an appropriate move for the subsequent round. For efficiency in processing lists, we suppose that the list of moves is given in reverse order, with the last move first.

For example, the
copy1
strategy is implemented by

The first move is an arbitrary choice of
Rock
, The second strategy
smart1
is implemented by

smart1 :: Strategy1

smart1 ms = if null ms then Rock

else pick (foldr count (0,0,0) ms)

count :: Move -> (Int,Int,Int) -> (Int,Int,Int)

count Paper (p,r,s)
= (p+1,r,s)

count Rock (p,r,s)
= (p,r+1,s)

count Scissors (p,r,s)
= (p,r,s+1)

pick :: (Int,Int,Int) -> Move

pick (p,r,s)

| m < p
= Scissors

| m < p+r
= Paper

| otherwise = Rock

where m = rand (p+r+s)

This strategy counts the number of times each move has been made, and uses the results to pick a move. The value of
rand
applied to
n
is some integer
m
in the range 0 ≤
m
<
n
. (Note that
rand
is never applied to the same integer.) Thus the choice of move depends on whether
m
falls in one of the three ranges 0 ≤
m
<
p
or
p
≤
m
<
p
+
r
or
p
+
r
≤
m
<
p
+
r
+
s
.

For example, if
p
is large, then
Scissors
will be chosen with high probability (because scissors cuts paper); and if
r
is large, then
Paper
will be chosen with high probability (because paper wraps rock); and so on. To define
rand
we can make use of two functions in the library
System.Random
:

rand :: Int -> Int

rand n = fst $ randomR (0,n-1) (mkStdGen n)

The function
mkStdGen
takes an integer and returns a random number generator, likely to be different for different integers. The choice of argument to
mkStdGen
is arbitrary, and we have simply chosen
n
. The function
randomR
takes a range (
a
,
b
) and a random number generator, and returns a pseudo-random integer
r
in the range
a
≤
r
≤
b
and a new random number generator.

We can now define
rounds1
:

The function
extend
adds a new pair of moves to the front of the list of existing rounds, and
rounds1
generates the infinite list of rounds by repeatedly applying
extend
to the initially empty list. It is more efficient to add something to the front of a list than to the end, which is why we keep the list of moves in reverse order.

Nevertheless
rounds1
is inefficient. Suppose a strategy takes time proportional to the length of its input to compute the next move. It follows that
extend
takes Θ(
n
) steps to update a game of
n
rounds with a new round. Therefore, it takes Θ(
N
²
) steps to compute a game of
N
rounds.

For comparison, let’s consider another way we might reasonably represent strategies. This time we take
type Strategy2 = [Move] -> [Move]

In the new representation, a strategy is a function that takes the potentially infinite list of moves made by the opponent and returns the potentially infinite list of replies. For example, the copy strategy is now implemented by

copy2 :: Strategy2

copy2 ms = Rock:ms

This strategy returns
Rock
the first time, and thereafter returns just the move made by the opponent in the previous round. The smart strategy is reprogrammed as

smart2 :: Strategy2

smart2 ms = Rock:map pick (stats ms)

where stats = tail . scanl (flip count) (0,0,0)

The function
stats
computes the running counts of the three possible moves. This strategy, like
copy2
, is also efficient in that it produces each successive output with constant delay.

With this new model of strategies we can redefine the function
rounds
:

rounds2 :: (Strategy2,Strategy2) -> [Round]

rounds2 (p1,p2) = zip xs ys

where xs = p1 ys

ys = p2 xs

Here,
xs
is the list of replies computed by the first player in response to the list
ys
which, in turn, is the list of replies made by the second player in response to the list of moves
xs
. Thus
rounds2
is defined by two cyclic lists and we are obliged to show that it does indeed generate an infinite list of well-defined moves. More on this below. If the two players do encapsulate legitimate strategies, then
rounds2
computes the first
n
moves of the game in Θ(
n
) steps, assuming that both players compute each new move with constant delay. Thus the second method for modelling strategies leads to a more efficient program than the earlier one.

Unfortunately, there is a crucial flaw with the second representation of strategies: it offers no protection against someone who cheats! Consider the strategy

cheat ms = map trump ms

trump Paper
= Scissors

trump Rock
= Paper

trump Scissors = Rock

The first reply of
cheat
is the move guaranteed to beat the opponent’s first move; similarly for subsequent moves. To see that
cheat
cannot be prevented from subverting the game, consider a match in which it is played against
copy2
, and let
xs = cheat ys
and
ys = copy2 xs
. The lists
xs
and
ys
are the limits of the two chains {
xs
_n
| 0 ≤
n
} and {
ys
_n
| 0 ≤
n
}, where
xs
₀
=
⊥ and
xs
_n
+1
= cheat ys
_n
, and
ys
₀
=
⊥ and
ys
_n
+1
= copy2 xs
_n
. Now, we have

Continuing in this way, we see that the limits of these sequences are indeed infinite lists of well-defined moves. Moreover,
cheat
always triumphs. Another cheating strategy is given by
devious :: Int -> Strategy2

devious n ms = take n (copy2 ms) ++ cheat (drop n ms)

This strategy behaves like copy for
n
moves then starts to cheat.

Can we find a way to protect against cheats? To answer this question, we need to take a closer look at what constitutes an honest strategy. Informally speaking, a strategy is honest if its first move is computed in the absence of any information about the opponent’s first move, the second move is computed without any information about the opponent’s second move, and so on. Moreover, each of these moves should be well-defined, given that the opponent’s moves are well-defined. More precisely, let
wdf
(
n
,
ms
) denote the assertion that the first
n
elements in the
(possibly partial) list of moves
ms
are well-defined. Then a strategy
f
is
honest
if
wdf
(
n
,
ms
) ⇒
wdf
(
n
+1,
f
(
ms
))

for all
n
and
ms
. It is easy to show that
copy2
is honest. On the other hand,
cheat
is not honest because
wdf
(0, ⊥) is true but
wdf
(1,
cheat
⊥) is false. The strategy
dozy
, where
dozy ms = repeat undefined

is also dishonest according to this definition although it doesn’t actually cheat.

Having identified the source of criminal or lackadaisical behaviour, can we ensure that only honest strategies are admitted to the game? The answer is a qualified yes: although it is not possible for a mechanical evaluator to recognise cheating (in the same way that it is not possible to recognise ⊥, or strategies that do not return well-defined moves), it is possible to define a function
police
so that if
p
is an honest player and
ms
is an infinite sequence of well-defined moves, then
police p ms = p ms
. On the other hand, if
p
is dishonest at some point, then the game ends at that point in ⊥. Operationally speaking,
police
works by forcing
p
to return the first (well-defined!) element of its output before it gives
p
the first element of its input. Similarly for the other elements. The definition is

police p ms = ms' where ms' = p (synch ms ms')

synch (x:xs) (y:ys) = (y `seq` x):synch xs ys

Recall from
Chapter 7
that
x `seq` y
evaluates
x
before returning the value of
y
. The proof that this implementation meets its specification is rather involved, so we are not going into details. It follows from the above analysis that to prevent cheating we must rewrite the definition of
rounds2
to read

rounds2 (p1,p2) = zip xs ys

where xs = police p1 ys

ys = police p2 xs

In the paper–rock–scissors game we modelled interaction by a function that took an infinite list of moves and returned a similar list. The same idea can be used to provide a simple model of input–output interaction. It’s called
stream-based
interaction because infinite lists are also called streams. Haskell provides a function
interact :: ([Char] -> [Char]) -> IO ()

for interacting with the world. The argument to
interact
is a function that takes a potentially infinite list of characters from the standard input channel, and returns a potentially infinite list of characters to be typed on the standard output channel.

For example,

ghci> import Data.Char

ghci> interact (map toUpper)

hello world!

HELLO WORLD!

Goodbye, cruel world!

GOODBYE, CRUEL WORLD!

{Interrupted}

We imported the library
Data.Char
to make
toUpper
available, and then created an interaction that capitalised each letter. Each time a line of input was typed (and echoed) the interaction produced the same line in capital letters. The process continues until we interrupt it.

We can also design an interactive program that terminates. For example,

interact (map toUpper . takeWhile (/= '.'))

will interact as above but terminate as soon as a line containing a period is typed:

ghci> interact (map toUpper . takeWhile (/= '.'))

Goodbye. Forever

GOODBYE

Finally, here is a stand-alone program that takes a literate Haskell file as input and returns a file in which all nonempty lines not beginning with
>
are removed. The remaining lines are modified by removing the
>
character, so the result is a legitimate
.hs
file (a Haskell script not using the literate style):