Editing Cons (section)

==Functional implementation==
Since Lisp has [[first-class function]]s, all data structures, including cons cells, can be implemented using functions. For example, in [[Scheme (programming language)|Scheme]]:
<syntaxhighlight lang="scheme">
(define (cons x y)
  (lambda (m) (m x y)))
(define (car z)
  (z (lambda (p q) p)))
(define (cdr z)
  (z (lambda (p q) q)))
</syntaxhighlight>
This technique is known as [[Church encoding#Church pairs|Church encoding]]. It re-implements the ''cons'', ''car'', and ''cdr'' operations, using a function as the "cons cell". Church encoding is a usual way of defining data structures in pure [[lambda calculus]], an abstract, theoretical model of computation that is closely related to Scheme.

This implementation, while academically interesting, is impractical because it renders cons cells indistinguishable from any other Scheme procedure, as well as introduces unnecessary computational inefficiencies.

However, the same kind of encoding can be used for more complex algebraic data types with variants, where it may even turn out to be more efficient than other kinds of encoding.<ref>{{cite web |url=http://www.st.cs.ru.nl/papers/2006/janj2006-TFP06-EfficientInterpretation.pdf |title=Efficient Interpretation by Transforming Data Types and Patterns to Functions |accessdate=2009-03-01 |url-status=dead |archiveurl=https://web.archive.org/web/20100331083602/http://www.st.cs.ru.nl/papers/2006/janj2006-TFP06-EfficientInterpretation.pdf |archivedate=2010-03-31 }}</ref>
This encoding also has the advantage of being implementable in a statically typed language that doesn't have variants, such as [[Java (programming language)|Java]], using interfaces instead of lambdas.