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.