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

You can quite trivially define a class that behaves much like cons:

class Cons(object):
    def __init__(self, car, cdr):
        self.car = car
        self.cdr = cdr

However this will be a very 'heavyweight' way to build basic data structures, which Python is not optimised for, so I would expect the results to be much more CPU/memory intensive than doing something similar in Lisp.

Answer 2

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 3

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 4

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 5

No. cons is an implementation detail of Lisp-like languages; it doesn't exist in any meaningful sense in Python.