therning.org/ magnus

First off, keep in mind that the State st a type is a function type (st -> (st, a)) and that returnState a wraps a into a function that returns a state-value,value pair when it’s applied to a state-value.

bindState is a bit complicated to think about. It takes two arguments, both functions. The first (m) is of type st -> (st, a) (i.e. State st a). The second (k) is of type a -> (st -> (st, b)) (i.e. a-> (State st b)). In other words, this second argument is a function that takes a value and returns a function that we can apply to a state, the return function has “wrapped up” in it the end result of the computation. Looking more into the implementation of bindState we see that it returns a function taking one argument (st) where m is used to calculate a new state-value,value (st' and a) pair based on st. Next k is used to “wrap” a into a function (m') that we can apply a state_value to. The last step is to apply the new state (st') to the function wrapping the new value (m').

Looking at mapTreeStateM on (Leaf a) we see that f a is m in bindState. \b -> returnState (Leaf b), from our look at bindState we can see that b here will be our newly calculated value (i.e. the new value coming out of f a will be wrapped into a leaf again).

I found it easier to understand when I applied an “identity function” to a tree:

doNothing :: Integer -> State Integer Integer
doNothing a = returnState a

Working through, on paper, what goes on when applying doNothing, a tree of one leaf, and an initial state of 0 made it quite clear what is happening.

Analysing the recursive step after this is fairly straight forward. Adding parentheses makes it a bit easier to read and I found it helpful to rewrite it to only consider the left branches:

mapTreeStateMLO :: (a -> State st Integer) -> Tree a -> State st (Tree Integer)
mapTreeStateMLO f (Leaf a) =
    (f a) `bindState` (\b -> returnState (Leaf b))
mapTreeStateMLO f (Branch lhs rhs) =
    (mapTreeStateMLO f lhs) `bindState` (\lhs' ->
    returnState (Branch lhs' (Leaf (-1))))

The extension to right branches comes fairly naturally after that.

I wrote a few functions to play with mapTreeStateM. All of them use a single integer to represent its state.

State is the number of leaves in the tree:

countLeaf :: Integer -> State Integer Integer
countLeaf a = \st -> (st + 1, a)

State is the maximum value of a leaf

maxLeaf :: Integer -> State Integer Integer
maxLeaf a = \st -> (max st a, a)

This function that numbers each leaf in the tree.

numberLeaf :: Integer -> State Integer (Integer, Integer)
numberLeaf a = \st -> (st + 1, (st, a))

If there’s a type Foo a b, then it’s possible to access a and b in a function definition through the notation f@(x y):

bar :: Foo a b -> Int
bar f@(x y) = ...

Very handy indeed.

• Computation wraps a result of a function in a type.
• augment strips the type, applies a function to the result. The function must wrap the end result in the type again.
• combine “joins” two results together.

Making [] and instance of Computation illustrates it the best. Maybe and Failable are a bit “funny” because the combine works like or, i.e. they take the first success x and run with it.

Getting searchAll to work requires a type definition.

 searchAll :: Graph  v e -> Int Int -> Maybe [Int]

or

 searchAll :: Graph  v e -> Int Int -> Failable [Int]

or

 searchAll :: Graph  v e -> Int Int -> [[Int]]

How I think about searchAll:

1. src == dst is a successful end state. The result is [src] wrapped in success.
2. Running out of edges in the inner function (search') is an unsuccessful end state. The result is a string wrapped in failure.
3. The first recursive step for search' (src == u) walks us one step on the way (u -> v).
   1. The call to searchAll returns a wrapped result (i.e. path(s) from v to dst),
   2. we augment this result by sticking u in front of it (for the list-based Computation that means mapping u: on each path, for the others it means dropping the “wrapper type” and calling (u:) on the actual result), then
   3. we wrap it all up again.
   4. Finally we combine it with the result of a search' on the other edges. The combine in the case of lists is concatenation, i.e. we add our list of current results to all other results. For the other two combine is a “pick first” operation.
4. The other recursive step for search' simply looks for results in all remaining edges since the current edge isn’t part of our path.

Now I can go on to read about monads.