Represent a list 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. New to topics? Read the docs here!