LISP cons in python

WARNING AHEAD: The material below may not be practical!

Actually, cons needs not to be primitive in Lisp, you can build it with λ. See Use of lambda for cons/car/cdr definition in SICP for details. In Python, it is translated to:

def cons(x, y):
    return lambda pair: pair(x, y)

def car(pair):
    return pair(lambda p, q: p)

def cdr(pair):
    return pair(lambda p, q: q)

Now, car(cons("a", "b")) should give you 'a'.

How is that? Prefix Scheme :)

Obviously, you can start building list using cdr recursion. You can define nil to be the empty pair in Python.

def nil(): return ()

Note that you must bind variable using = in Python. Am I right? Since it may mutate the variable, I'd rather define constant function.

Of course, this is not Pythonic but Lispy, not so practical yet elegant.

Exercise: Implement the List Library http://srfi.schemers.org/srfi-1/srfi-1.html of Scheme in Python. Just kidding :)

In Python, it's more typical to use the array-based list class than Lisp-style linked lists. But it's not too hard to convert between them:

def cons(seq):
    result = None
    for item in reversed(seq):
        result = (item, result)
    return result

def iter_cons(seq):
    while seq is not None:
        car, cdr = seq
        yield car
        seq = cdr

>>> cons([1, 2, 3, 4, 5, 6])
(1, (2, (3, (4, (5, (6, None))))))
>>> iter_cons(_)
<generator object uncons at 0x00000000024D7090>
>>> list(_)
[1, 2, 3, 4, 5, 6]

Note that Python's lists are implemented as vectors, not as linked lists. You could do lst.insert(0, val), but that operation is O(n).

If you want a data structure that behaves more like a linked list, try using a Deque.