= Difference list
{title2=`[a] -> [a]`}
Represent a <list> $xs$ by the <function> `\ys -> xs ++ ys`. Concatenation becomes function composition, the empty list is represented by `id`, and applying to `[]` recovers the list. Only functions of this tail-prepending form are valid representations; arbitrary functions of the displayed type need not satisfy the invariant. A higher-order <tree fold> using difference lists produces an inorder traversal in linear time on every tree shape.
Back to article page
