static :: Board -> Double
Episode Two: Designing with functions and composition
In episode one, we have seen how lazy evaluation allows us to separate the generation of potentially infinite data structures from functions that work on it. We will now follow up on the same example from a different angle: how to design with functions for incremental development.
So far we have developed means for building a tree of game boards where child nodes represent the boards that result from the players mutually placing their moves.
In order to find the next best move we have to give some value to a board such that we can pick the one with the
highest value. Let’s go with a Double value where 1
represents that the computer has won and -1
for the opponent.
A function that tells us the static value of a board has this type:
For the purpose of our discussion, we don’t need to know how it is implemented for our special game. If you are curious, you find a simple valuation for the tic tac toe game here.
So when we consider our possible moves, we would pick the one that leads to the board with the highest value - at least if we only look one move ahead. As soon as we look a little further, we also have to consider what our opponent does. It is reasonable to assume that he will also do his best move, which for him is the one with the lowest value. And he in turn will assume that we do our best, and so it goes on.
That is to say that the static value of a board is only interesting for the leaves in our tree. All other values are derived from the maximum/minimum value one level below. Here is a figure that calculates the next move for a given board. Note that the static valuation is in circles, the minimax value has no circle around it.
Here is the natural way of putting this into a functional design:
maximize :: Ord a => Tree a -> a
maximize (Node a []) = a
maximize (Node a children) = maximum (map minimize children)
minimize :: Ord a => Tree a -> a
minimize (Node a []) = a
minimize (Node a children) = minimum (map maximize children)
Is this really "natural"? Yes.
The functional way assumes the least what is needed (the "weakest precondition" like in Hoare proofs).
In order to minimax a tree, we only need to assume that the payload can be ordered in some way
(in Java terms, it is "comparable"). In the type annotation Tree a → a
the "a" is a type variable.
It tells that our method maps from a tree of "a" payloads to a value of exactly that type "a".
The only thing that we assume about the "a" type is the Ord a ⇒
constraint,
i.e. the "a" type must be an instance of the Ord
typeclass such that we can call minimum
and maximum
on a list thereof.
There is a second indication that such an early abstraction is a normal thing to do: we can totally delete the type declarations and let Frege infer the types. Guess what. It will exactly infer the types that we have given! What can be more natural than that?
Thanks to this early abstraction, we have a totally generic solution for the minimaxing of trees, which is fully independent of our game trees. Again, we have made a non-intrusive increment.
But does it work? In our game tree, "a" is of type Board
and boards are not (yet) comparable.
This is where function composition appears again.
We have already seen it when we composed the pruning function with the gameTree
to produce a
prunedTree
as prune 5 . gameTree
.
By the same means we can make a tree of boards into a tree of the static
values of those boards.
valueTree = fmap static . prunedTree
Remember that the tree is not materialized! Only on demand when we access the children will they be built.
And so it is as well for the static
function: nothing gets evaluated before we access the payload via static board
.
The function that calculates the maximum value for a board is again a composition:
maximize . valueTree
or in its expanded form:
maxValue = maximize . fmap static . prune 5 . gameTree
We now have a set of functions that we can compose to our liking.
The compiler will infer all the types and makes sure that they properly line up.
For example, we cannot accidentally maximize
a tree of values that don’t define an order.
But we can have such trees - actually, gameTree
is of that nature.
The types tell us that we can happily prune
before or after calling fmap static
while they catch errors such as putting prune
in a place where it cannot work.
This is not only a nice toolbox to play with. It is compositional in more than one meaning of the word. We have come to this point in a fully non-intrusive, incremental manner, never going back to change previously defined functions or data types.
In episode three we will do incremental development with the help of higher-order functions and typeclasses. The goal will be to show a forecast of how we think the game will develop.