blog

One way to define laziness is as follows: a language has strict evaluation if and only if \(f(\bot) = \bot\) for every function \(f\) definable in the language.

We can use this definition to solve another problem: comparing algorithms across lazy and strict languages. In particular, it allows us to ask questions like "how many superfluous computations does this traversal perform in a strict language?"

We can form a xiphophyllous tree from an algebraic data type by simply calling its constructors with undefined as an argument, viz.

import Data.List (partition)
evens :: [a] -> [a]
evens = fmap snd . fst . partition (even . fst) . zip [0..]
list :: [String]
list = ["a", undefined, "b", undefined, "c", undefined, "d", undefined]

You can then verify that evens list evaluates to ["a", "b", "c", "d"], as desired. We say that the application of evens to list is xiphophyllous of degree \(\frac{1}{2}\); this function will visit half as many leaves in a lazy language as it would in a strict one.

In fact, this generalizes to arbitrary inductively defined data types; when the number of nodes that can be ignored is finite, the minimum of such is well-defined.