Recursive Functions of Symbolic Expressions

app.coffee

# Elementary List Functions
cons = (a, b) -> (option) -> switch option
  when true then a
	else b
nil = null
atom = (x) -> typeof(x) != 'function'
car = (x) -> x(true)
cdr = (x) -> x(false)

# Functions on Recursive Pairs
ff = (list) -> switch
    when atom(car(list)) then car(list)
    else ff(car(list))
subst = (a, b, x) -> switch
    when atom(x) then (switch
        when x == b then a
        else x)
    else cons(subst(a, b, car(x)), subst(a, b, cdr(x)))
equal = (x, y) -> (atom(x) and atom(y) and x == y) or 
				  (not atom(x) and not atom(y) and 
				  equal(car(x), car(y)) and 
				  equal(cdr(x), cdr(y)))				  
				  
# Utilities for Viewing Nested Pairs as Lists				  
_ = (members...) -> switch members.length
	when 0 then nil
	else cons(members[0], _.apply({}, members.slice(1)))
isNil = (x) -> atom(x) and x == nil

# List Access Shorthands
caar = (x) -> car(car(x))
cadr = (x) -> car(cdr(x))
caddr = (x) -> car(cdr(cdr(x)))
cadar = (x) -> car(cdr(car(x)))

# Recursive Functions on Lists
append = (x,y) -> switch
    when isNil(x) then y
    else cons(car(x), append(cdr(x), y))
among = (x,y) -> not isNil(y) and (equal(x, car(y)) or among(x, cdr(y)))
pair = (x,y) -> switch
    when isNil(x) and isNil(y) then nil
    when not atom(x) and not atom(y) then cons(cons(car(x), cons(car(y), nil)), pair(cdr(x), cdr(y)))
    else nil
assoc = (x,y) -> switch
    when caar(y) == x then cadar(y)
    else assoc(x, cdr(y))
sub2 = (x,z) -> switch
    when isNil(x) then z 
    when equal(caar(x), z) then cadar(x)
    else sub2(cdr(x), z)
sublis = (x, y) -> switch
    when atom(y) then sub2(x, y)
    else cons(sublis(x, car(y)), sublis(x, cdr(y)))    

# A Function for Outputting a List
LIST = (list) -> switch
	when isNil(list) then "[]"
	when atom(list) then list
	else "("+LIST(car(list))+"):"+LIST(cdr(list))
output = (x) -> console.log(LIST(x))