Ross Paterson: Arrows and Computation introduces the trace
function (on page 11):
trace :: ((a, c) -> (b, c)) -> a -> b
trace f a = let (b, c) = f (a, c) in b
The trace
function is useful for modularizing the magic feedback step in circular programs. For example, consider Richard Bird's famous repmin
function which finds the minimum leaf value of a tree and creates an identical tree with every leaf value replaced by the minimum leaf value, both in a single pass by making clever use of lazy evaluation and local recursion (as provided by letrec
):
data Tree = Leaf Int | Node Tree Tree deriving Show
repmin :: Tree -> Tree
repmin = trace repmin'
repmin' :: (Tree, Int) -> (Tree, Int)
-- put the minimum value m into the leaf and return the old value n as the minimum
repmin' (Leaf n, m) = (Leaf m, n)
-- copy the minimum value m into both the left and right subtrees and
-- set the minimum value m to the minimum of both the left and right subtrees
repmin' (Node l r, m) = let (l', lmin) = repmin' l m in
let (r', rmin) = repmin' r m in
(Node l' r', lmin `min` rmin)
Anyway, I was wondering how to implement the trace
function in JavaScript such that we can implement repmin
as follows:
const Leaf = (value) => ({ tag: "Leaf", value });
const Node = (left, right) => ({ tag: "Node", left, right });
const repmin = trace(function repmin(tree, min) {
switch (tree.tag) {
case "Leaf":
return [Leaf(min), tree.value];
case "Node":
const [left, lmin] = repmin(tree.left, min);
const [right, rmin] = repmin(tree.right, min);
return [Node(left, right), Math.min(lmin, rmin)];
}
});
In order to implement trace
we need local recursion as provided by letrec
so that we can write something like:
const trace = (f) => (a) => {
const [b, c] = f(a, c);
return b;
};
I originally thought of making c
a promise. However, that changes the semantics of trace
. So, can you think of a way to implement trace
in JavaScript without changing its semantics?
Actually, you only need lazy evaluation because assignments in JavaScript are like
letrec
. Lazy evaluation is generally implemented using thunks. Hence, you can implementtrace
as follows:Using this definition of
trace
, therepmin
function can remain the same:However, you'd want to make your data constructors possibly lazy using getters:
Putting it all together:
The only problem is that you won't be able to write functions like:
This is because the
*
operator is not lazy. Hence, you would have to define a lazymul
function:Hope that helps.