LISP cons in python

Question

Is there an equivalent of cons in Python? (any version above 2.5)

If so, is it built in? Or do I need easy_install do get a module?

Answer 1

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 :)

Answer 2

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]

Answer 3

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.

Answer 4

In Python 3, you can use the splat operator * to do this concisely by writing [x, *xs]. For example:

>>> x = 1
>>> xs = [1, 2, 3]
>>> [x, *xs]
[1, 1, 2, 3]

If you prefer to define it as a function, that is easy too:

def cons(x, xs):
  return [x, *xs]