4 ms·
Here's my implementation, using tuples. But bear in mind that for almost everything Python's used for, Python lists (i.e. vectors) are good enough. def cons(
by DonaldFisk 10y ago
Here's my implementation, using tuples. But bear in mind that for almost everything Python's used for, Python lists (i.e. vectors) are good enough.
def cons(x, y):
return (x, y)
def car(x):
return x if x == () else x[0]
def cdr(x):
return x if x == () else x[1]
def append(x, y):
return y if x == () else cons(car(x), append(cdr(x), y))
def rev(x, y):
return y if x == () else rev(cdr(x), cons(car(x), y))
def reverse(x):
return rev(x, ())
def null(x):
return x == ()
def list(*tuple):
if len(tuple) < 1:
return ()
else:
x = ()
for i in reversed(range(len(tuple))):
x = cons(tuple[i], x)
return x
def mapcar(fn, x):
return () if x == () else cons(apply(fn, (car(x),)), mapcar(fn, cdr(x)))
----------------------
>>> import sexpr
>>> print sexpr.cons(1, 2)
(1, 2)
>>> x = sexpr.list(1, 2, 3, 4)
>>> print x
(1, (2, (3, (4, ()))))
>>> print sexpr.reverse(x)
(4, (3, (2, (1, ()))))
>>> print x
(1, (2, (3, (4, ()))))
>>> print sexpr.append(x, sexpr.cdr(sexpr.reverse(x)))
(1, (2, (3, (4, (3, (2, (1, ())))))))
>>> print sexpr.mapcar(lambda y : y ∗ y, x)
(1, (4, (9, (16, ()))))
- sn9 10y agoShouldn't cdr be changed so that it gives the list that doesn't contain the first element? def cdr(x): return x if x == () else x[1:]
- DonaldFisk 10y ago# No. x = sexpr.list(1, 2, 3, 4) >>> print x (1, (2, (3, (4, ())))) >>> print sexpr.cdr(x) (2, (3, (4, ()))) # which is what you want. >>> def cdr2(x): return x if x == () else x[1:] ... >>> print cdr2(x) ((2, (3, (4, ()))),) # which is wrong.
- sn9 10y agoBut that's how it's used in Lisp, which is where car and cdr are used. (car x) is the first sexp in x and (cdr x) is x without the first sexp.
- DonaldFisk 10y agoYou are mistaken. In Lisp, lists are constructed out of NIL and dotted pairs, so, (1 . (2 . (3 . NIL))) = (1 2 3) I chose to implement lists in Python in the same way, out of () and 2-element tuples. So (1 2 3) = (1 . (2 . (3 . NIL))) in Lisp which becomes (1, (2, (3, ())) in Python. (cdr '(1 2 3)) = (2 3) = (2 . (3 . NIL)) which should therefore be (2, (3, ())) in Python, i.e. the second element of the 2-element tuple (1, (2, (3, ())), NOT the 1-element tuple ((2, (3, ())),) obtained by removing the first element. I should point out that there is one difference, in case anyone else spots it: tuples in Python are immutable, whereas dotted pairs in Lisp are not, so my implementation won't allow rplaca and rplacd.
- deleted 10y ago[deleted]