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.
Read more about this topic: Cons
Famous quotes containing the words technically and/or fundamental:
“When you see something that is technically sweet, you go ahead and do it and you argue about what to do about it only after you have had your technical success. That is the way it was with the atomic bomb.”
—J. Robert Oppenheimer (1904–1967)
“What is wanted—whether this is admitted or not—is nothing less than a fundamental remolding, indeed weakening and abolition of the individual: one never tires of enumerating and indicting all that is evil and inimical, prodigal, costly, extravagant in the form individual existence has assumed hitherto, one hopes to manage more cheaply, more safely, more equitably, more uniformly if there exist only large bodies and their members.”
—Friedrich Nietzsche (1844–1900)