Mogensen–Scott encoding¶
Mogensen–Scott encoding represents constructor data as functions that select a matching handler and expose immediate fields.
Core Idea¶
A Scott-style encoded value is a function that takes one handler for each data constructor, selects its own constructor's handler and passes its immediate fields. Mogensen used the same dispatch idea, with higher-order syntax for binding, to encode lambda terms as lambda-calculus data. The compound name should not imply that Mogensen originated every Scott-style encoding.[ref-35df2886f374][ref-b19705807964]
Scope of Application¶
In pure lambda calculus this implements case analysis without a primitive case. For Peano numerals, Zero = λz s.z and Succ n = λz s.s n. For Mogensen's lambda terms, variable, application and abstraction select three distinct handlers; abstraction passes a host lambda for its bound body. A separate self-interpreter, not constructor selection alone, performs evaluation.[ref-35df2886f374][ref-b19705807964]
Clarity¶
Let pred = λn.n Zero (λp.p). Applied to Succ (Succ Zero), the successor branch receives the stored Succ Zero and returns it; applied to Zero, the zero branch returns Zero. That is one-layer deconstruction in a few beta steps, not a guarantee about wall-clock time. Mogensen's original p. 348 encoding of λx.xx selects abstraction at the root, application in the body, then variable for each x: subterm codes are passed, not already evaluated.[ref-35df2886f374][ref-b19705807964]
Manages Complexity¶
Count the constructors and give a handler for each. Which handler runs identifies the constructor, and its arguments are the fields. This separates quotation, one-layer inspection and recursive interpretation. A whole-structure traversal still needs an external recursor or fixed point.[^ref-35df2886f374]
Abstract Reasoning¶
Replace the immediate recursive child with a pre-folded result and the representation becomes Church-like. Scott encoding favors local deconstruction; Church-style folding favors whole-structure elimination already embodied in the value. Which is convenient depends on the operation, not a universal speed ranking.[ref-b19705807964][ref-eb749038377a]
Knowledge Transfer¶
The dispatch equations transfer to finite-constructor types when arities and handler order are explicit. This is a specialized Encoding and Decoding pattern, not a name for every Scott encoding. Mogensen's binder representation is a specific extension for lambda syntax; recursive children are not assumed pre-folded.[^ref-35df2886f374]
[^ref-35df2886f374]: Torben Æ. Mogensen, “Efficient Self-Interpretation in Lambda Calculus,” JFP 2(3) (1992), 345–364, pp. 347–349. [^ref-b19705807964]: Ben Lynn, “The Scott encoding”, original worked construction. [^ref-eb749038377a]: Jan Martin Jansen, “Programming in the λ-Calculus: From Church to Scott and Back” (2013), publisher abstract.
Relationships to Other Abstractions¶
Current abstraction Mogensen–Scott encoding Domain-specific
Parents (1) — more general patterns this builds on
-
Mogensen–Scott encoding is a kind of Encoding And Decoding Prime
Mogensen–Scott is a constructor encoding.
Hierarchy path (1) — routes to 1 parentless root
- Mogensen–Scott encoding → Encoding And Decoding → Transformation → Function (Mapping)
Neighborhood in Abstraction Space¶
Mogensen–Scott encoding sits in a sparse region of the domain-specific corpus (76th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Type Systems & Functional Constructs (18 abstractions)
Nearest neighbors
- Programming Fold — 0.86
- L-Attributed Grammar — 0.84
- Tacit Programming — 0.83
- Anonymous Function — 0.83
- Paramorphism — 0.82
Computed from structural-signature embeddings · 2026-10-08