Defunctionalization

Defunctionalisation is a technique that replaces higher-order function values with a first-order representation. Instead of passing lambdas or closures directly, you encode the possible operations as constructors of an algebraic data type and interpret them with an application function.

The code below shows this transformation for a small list fold example. The higher-order fold accepts a combining function, while fold' accepts an Arrow value whose behaviour is defined by apply.

Why Use It?

• Explicit representation: The set of supported operations becomes a closed data type that can be inspected and manipulated.
• Captured values become data: The n in FPlusCons n is stored as a constructor field rather than hidden inside a closure.
• Type safety with GADTs: The Arrow GADT records the input and output types for each encoded operation.
• A first-order core: Higher-order control flow is replaced by a small interpreter, which can simplify analysis or later compilation passes.

Key Principle

The main tradeoff is that first-class functions are replaced with a closed set of function tags plus an interpreter. In this example, (+) and x xs -> x + n : xs become the constructors FPlus and FPlusCons, and apply performs the work that the original function values did.

References

• Compiling higher order functions with GADTs
• Lightweight higher-kinded polymorphism