Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

LISP cons in python

Tags:

python

lisp

cons

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?

like image 781
tekknolagi Avatar asked Nov 10 '11 01:11

tekknolagi


4 Answers

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

like image 161
Alex Vong Avatar answered Oct 14 '22 19:10

Alex Vong


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]
like image 44
dan04 Avatar answered Oct 14 '22 19:10

dan04


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.

like image 3
A B Avatar answered Oct 14 '22 18:10

A B


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]
like image 3
dionyziz Avatar answered Oct 14 '22 17:10

dionyziz