Defunctionalization

The following is a Haskell translation of an example due to Olivier Danvy. Consider the Tree datatype and the following program. data Tree a = Leaf a | Node (Tree a) (Tree a) cons :: a -> [a] -> [a] cons x xs = x : xs o :: (b -> c) -> (a -> b) -> a -> c o f g x = f (g x) flatten :: Tree t -> [t] flatten t = walk t [] walk :: Tree t -> [t] -> [t] walk (Leaf x) = cons x walk (Node t1 t2) = o (walk t1) (walk t2) Defunctionalization replaces all higher-order functions (in this case, o is the only higher-order function) with a value of the Lam datatype. Instead of calling higher-order functions directly, it introduces an apply function that interprets the Lam datatype. data Lam a = LamCons a | LamO (Lam a) (Lam a) apply :: Lam a -> [a] -> [a] apply (LamCons x) xs = x : xs apply (LamO f1 f2) xs = apply f1 (apply f2 xs) cons_def :: a -> Lam a cons_def x = LamCons x o_def :: Lam a -> Lam a -> Lam a o_def f1 f2 = LamO f1 f2 flatten_def :: Tree t -> [t] flatten_def t = apply (walk_def t) [] walk_def :: Tree t -> Lam t walk_def (Leaf x) = cons_def x walk_def (Node t1 t2) = o_def (walk_def t1) (walk_def t2) ==See also==