Defunctionalization (Programming Languages) Defunctionalization
(d17n) is a whole program transformation that turns higher-order
functional programs into first-order ones. It's simplest to
divide it into four or five stages, though it is really a single
transformation. A simple example Let's use as an example a
completely pointless program that uses map twice: prog x ys =
(map aug ys, map sqr ys) where aug y = x + y sqr y = y ∗ y
Because d17n works on whole programs, we'll have to include the
defintion of map: map :: (Integer → Integer) → [Integer] →
[Integer] map f  =  map f (x:xs) = f x : map f xs (Note that, to
avoid complications, I've given map a type that contains no type
variables, despite the fact that its definition also supports
the more general type (α → β) → [α] → [β].) The first step is to
decode the dataflow, that is, to isolate the expressions that
create or use or pass on the value of higher-order arguments or
results. The simplest way of doing this is to introduce a data
type that encapsulate