In computer science, Scott encoding is a way to represent (recursive) data types in the lambda calculus.
Church encoding performs a similar function.
The data and operators form a mathematical structure which is embedded in the lambda calculus.
Whereas Church encoding starts with representations of the basic data types, and builds up from it, Scott encoding starts from the simplest method to compose algebraic data types.
This encoding allows the representation of lambda calculus terms, as data, to be operated on by a meta program.
Scott encoding appears first in a set of unpublished lecture notes by Dana Scott[1] whose first citation occurs in the book Combinatorial Logic, Volume II.
[2] Michel Parigot gave a logical interpretation of and strongly normalizing recursor for Scott-encoded numerals,[3] referring to them as the "Stack type" representation of numbers.
These values may then be accessed by applying the term to a function f. This reduces to, c may represent a constructor for an algebraic data type in functional languages such as Haskell.
This provides branching in the process flow, based on the constructor.
If the constructors have parameters, recursive data structures may be constructed.
of the data type D is Mogensen extends Scott encoding to encode any untyped lambda term as data.
The meta function mse converts a lambda term into the corresponding data representation of the lambda term; The "lambda term" is represented as a tagged union with three cases: For example, The Scott encoding coincides with the Church encoding for booleans.
of D above as[citation needed] compare this to the Mogensen Scott encoding, With this generalization, the Scott and Church encodings coincide on all enumerated datatypes (such as the boolean datatype) because each constructor is a constant (no parameters).
Concerning the practicality of using either the Church or Scott encoding for programming, there is a symmetric trade-off:[5] Church-encoded numerals support a constant-time addition operation and have no better than a linear-time predecessor operation; Scott-encoded numerals support a constant-time predecessor operation and have no better than a linear-time addition operation.