Circular Programming

Here is the data def­i­n­i­tion for a tree with only leaves.

data Tree =
    Leaf Int
  | Node Tree Tree
  deriv­ing (Show)

Sup­pose we want a func­tion minT that cal­cu­lates the min­i­mum val­ues of a tree. This is a straight-for­ward recur­sive func­tion.

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 com­pu­ta­tion. Now let’s con­sider some­thing else, say replac­ing 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 sec­ond com­pu­ta­tion. To do both com­pu­ta­tions we call the func­tions in sequence.

rep­And­Min­SeqT :: Tree -> Int -> (Tree, Int)
rep­And­Min­SeqT t z = (t', m)
  where t' = repT t z
        m  = minT t

This tra­verses the tree twice. How­ever, this is need­lessly inef­fi­cient since we can do this com­pu­ta­tion in par­al­lel by com­put­ing both prop­er­ties simul­ta­ne­ously. We can do this by just smash­ing repT and minT together.

rep­And­Min­ParT :: Tree -> Int -> (Tree, Int)
rep­And­Min­ParT (Leaf x) z = (Leaf z, x)
rep­And­Min­ParT (Node t u) z = (Node t' u', mt `min` mu)
  where (t', mt) = rep­And­Min­ParT t z
        (u', mu) = rep­And­Min­ParT u z

Instead of com­put­ing both prop­er­ties com­pletely inde­pen­dently, what if we want some depen­dency? Let’s say we want to replace each ele­ment of the tree with the min­i­mum value. This is no chal­lenge with our sequen­tial ver­sion. We’ll pass the result of our first com­pu­ta­tion, the out­put com­pu­ta­tion into our sec­ond, the aux­il­iary com­pu­ta­tion.

rep­With­Min­SeqT :: Tree -> Tree
rep­With­Min­SeqT t = t'
  where t' = repT t m
        m  = minT t

Fine, but can we do this in par­al­lel? Yes, with trace! Sim­ply call trace on rep­And­Min­ParT.

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

rep­With­Min­ParT :: Tree -> Tree
rep­With­Min­ParT = trace rep­And­Min­ParT

Here’s how you can think of trace in gen­eral.

• trace takes a func­tion f and pro­duces a new func­tion with a sin­gle input and out­put. The func­tion f take in two argu­ments i the input and z the aux­il­iary result. It com­putes two prop­er­ties in par­al­lel and returns them in a tuple.

• The first com­po­nent is the out­put com­pu­ta­tion and becomes the final result of trace f (in the above exam­ple it’s the tree replace­ment cal­cu­la­tion). The sec­ond is the aux­il­iary com­pu­ta­tion (in this exam­ple the cal­cu­la­tion of the min­i­mum leaf).

• trace binds z to the final value of the aux­il­iary com­pu­ta­tion. You are per­mit­ted to use this value whilst doing the out­put com­pu­ta­tion.