Cons - Not Technically Fundamental

Not Technically Fundamental

Since Lisp has first-class functions, all data structures, including cons cells, are not fundamentally necessary to the language, since all data structures can be implemented using functions. For example, in 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)))

The above code re-implements the cons, car, and cdr operations, using a function as the "cons cell". This is the 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 introducing 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. This encoding also has the advantage of being implementable in a statically typed language that doesn't have variants, such as Java, using interfaces instead of lambdas.