# Circular Programming

Here is the data definition for a tree with only leaves.

data Tree = Leaf Int | Node Tree Tree deriving (Show)

Suppose we want a function `minT`

that calculates the minimum values of a tree. This is a straight-forward recursive function.

minT :: Tree -> Int minT (Leaf x) = x minT (Node t u) = mt `min` mu where mt = minT t mu = minT u

We shall call `minT`

our first computation. Now let’s consider something else, say replacing all leaves with a fixed value `z`

repT :: Tree -> Int -> Tree repT (Leaf x) z = Leaf z repT (Node t u) z = Node t' u' where t' = repT t z u' = repT u z

This is our second computation. To do both computations we call the functions in *sequence*.

repAndMinSeqT :: Tree -> Int -> (Tree, Int) repAndMinSeqT t z = (t', m) where t' = repT t z m = minT t

This traverses the tree twice. However, this is needlessly inefficient since we can do this computation in parallel by computing both properties simultaneously. We can do this by just smashing `repT`

and `minT`

together.

repAndMinParT :: Tree -> Int -> (Tree, Int) repAndMinParT (Leaf x) z = (Leaf z, x) repAndMinParT (Node t u) z = (Node t' u', mt `min` mu) where (t', mt) = repAndMinParT t z (u', mu) = repAndMinParT u z

Instead of computing both properties completely independently, what if we want some dependency? Let’s say we want to replace each element of the tree with the minimum value. This is no challenge with our sequential version. We’ll pass the result of our first computation, the *output computation* into our second, the *auxiliary computation*.

repWithMinSeqT :: Tree -> Tree repWithMinSeqT t = t' where t' = repT t m m = minT t

Fine, but can we do this in parallel? Yes, with `trace`

! Simply call `trace`

on `repAndMinParT`

.

trace :: (a -> b -> (c, b)) -> a -> c trace f i = o where (o, z) = f i z repWithMinParT :: Tree -> Tree repWithMinParT = trace repAndMinParT

Here’s how you can think of `trace`

in general.

`trace`

takes a function`f`

and produces a new function with a single input and output. The function`f`

take in two arguments`i`

the input and`z`

the auxiliary result. It computes two properties in parallel and returns them in a tuple.The first component is the output computation and becomes the final result of

`trace f`

(in the above example it’s the tree replacement calculation). The second is the auxiliary computation (in this example the calculation of the minimum leaf).`trace`

binds`z`

to the*final value*of the auxiliary computation. You are permitted to use this value whilst doing the output computation.