Today we will look at a programming problem and a cool solution. I will assume basic Haskell knowledge. The problem is simple: “Given a binary tree with integers in its leaves, replace all the values in the leaves by the minimum of the tree.”
Lets give it a look. The tree is defined as follows
data Tree = Leaf Int | Node Tree Tree
deriving Show
The initial attempt would be to traverse the tree twice, one to evaluate the minimum and a different one to make the replacements. We can see this solution in the following snippet
transform :: Tree -> Tree
transform t = rep t (tmin t)
where rep (Leaf n) x = Leaf x
rep (Node lt rt) x = Node (rep lt x) (rep rt x)
tmin (Leaf n) = n
tmin (Node lt rt) = (tmin lt) `min` (tmin rt)
We can run ghci and see that it works fine
*Main> transform (Node (Node (Leaf 6) (Leaf 4)) (Leaf 1)) Node (Node (Leaf 1) (Leaf 1)) (Leaf 1)
but, can we do this with only one traversal?
The perks of being lazy
Haskell is a lazy language, by this I mean that it evaluates expressions only at need and as little as possible. For example, we can define an infinite list (usually called stream in other languages) like this:
ones :: [Int] ones = 1 : ones
If we try to print the list, the program will never stop. However, we can take as many elements as we want without any problem
*Main> take 1 ones [1] *Main> take 5 ones [1,1,1,1,1] *Main> take 10 ones [1,1,1,1,1,1,1,1,1,1]
Another cool thing we can do, is define the following function
trace :: ((a, b) -> (c, b)) -> a -> c
trace f i = o
where (o,z) = f (i,z)
The trace function gives the function f parts of its own output as an argument! Note that this is not recursion, this is called circular programming. This is not magic, the idea is that z will act as a pointer to a result we are expecting. Lets try to understand this by defining a function to solve our problem. This function, will take a pair, it first component will be a tree and the second parameter should represent something that we expect, in this case the minimum of the tree (an Int). So, we need something with the following specification.
repmin (t,n) = (rep t n, tmin t)
This states that n will hold the minimum of the tree and we make the replacements in the tree using this variable. Expanding the definition we get the following function
repmin :: (Tree, Int) -> (Tree, Int)
repmin (Leaf n , m) = (Leaf m , n)
repmin (Node l r, n) = (Node l' r', ln `min` rn)
where (l',ln) = repmin (l,n)
(r',rn) = repmin (r,n)
and if you have believed in me so far, we get that our solution to our problem is
transform' :: Tree -> Tree transform' = trace repmin
and… the moment of truth:
*Main> transform' (Node (Node (Leaf 6) (Leaf 4)) (Leaf 1)) Node (Node (Leaf 1) (Leaf 1)) (Leaf 1)
It worked!
Now, when can we use this idea? Basically, any time the function we give as a parameter to trace is not strict. By non strict, I mean that it doesn’t force the evaluation of its argument, (the components of the pair it takes as input). We will talk more about laziness and strictness on a different post. For now, I hope you enjoyed this short presentation, you can read more about circular programming here.
αβη 