Previously, I started practising recursions by implementing a type check on lat (list of atoms), and ismember (whether an atom is a member of a given lat). Then in the third chapter, named “Cons the Magnificent”, more list manipulation methods are being introduced.
The chapter started with the definition of rember, which is an abbreviation of ‘remove a member’. In other words, by providing an atom and a lat, the function returns a new lat, with the given atom removed from the original lat.
from primitives import *
from chap2 import *
def test_rember():
test_cases = (('mint',
('lamb', 'chops', 'and', 'mint', 'jelly'),
('lamb', 'chops', 'and', 'jelly')),
('mint',
('lamb', 'chops', 'and', 'mint', 'flavored', 'mint', 'jelly'),
('lamb', 'chops', 'and', 'flavored', 'mint', 'jelly')),
('toast',
('bacon', 'lettuce', 'and', 'tomato'),
('bacon', 'lettuce', 'and', 'tomato')),
('cup',
('coffee', 'cup', 'tea', 'cup', 'and', 'hick', 'cup'),
('coffee', 'tea', 'cup', 'and', 'hick', 'cup')),
('and',
('bacon', 'lettuce', 'and', 'tomato'),
('bacon', 'lettuce', 'tomato')),
('sauce',
('soy', 'sauce', 'and', 'tomato', 'sauce'),
('soy', 'and', 'tomato', 'sauce')))
for a, lat, expected in test_cases:
result = rember(a, lat)
assert result == expected
def rember(a, lat):
return (() if isnull(lat)
else cdr(lat) if iseq(a, car(lat))
else cons(car(lat), rember(a, cdr(lat))))
Just in case it wasn’t explained clearly in the previous post. The first thing to define in a recursive function is always the exit condition. In this case whether the lat is an empty list. Considering we are expecting a list from this function, it should then return an empty list to be constructed with the previous results (the cdr of a list with one element is always an empty list).
Also in this case we are removing only the first occurence of the given atom. So if we eventually encounter a car of the given lat being equal, then we would return the cdr of the lat (means excluding the car of the lat, as it is equal to the given atom). Lastly, if the given lat does not fall in the either condition, we shall construct a new lat with the car, and the result of rember of the cdr.
Next we are given the introduction of firsts. So given a list of lats, we are interested in the first element in each lat.
def test_firsts():
test_cases = (((('apple', 'peach', 'pumpkin'),
('plum', 'pear', 'cherry'),
('grape', 'raisin', 'pea'),
('bean', 'carrot', 'eggplant')),
('apple', 'plum', 'grape', 'bean')),
((('a', 'b'),
('c', 'd'),
('e', 'f')),
('a', 'c', 'e')),
((), ()),
((('five', 'plums'),
('four', ),
('eleven', 'green', 'oranges')),
('five', 'four', 'eleven')),
(((('five', 'plums'), 'four'),
('eleven', 'green', 'oranges'),
(('no', ), 'more')),
(('five', 'plums'), 'eleven', ('no', ))))
for l, expected in test_cases:
result = firsts(l)
assert result == expected
def firsts(l):
return (() if isnull(l)
else cons(car(car(l)), firsts(cdr(l))))
Practically, it is almost the same as the previous rember function. Except that there’s no extra condition besides checking if the lat is an empty list. So the function consumes one lat at a time from the given list (car of the given list), and construct a new lat by taking only the car of each lat.
Next, we are tyring to do something opposite of rember, which is the insertR function, where we are attempting to insert a new atom after a given atom, and return a new lat.
def test_insertR():
test_cases = (('topping',
'fudge',
('ice', 'cream', 'with', 'fudge', 'for', 'dessert'),
('ice', 'cream', 'with', 'fudge', 'topping', 'for', 'dessert')),
('jalapeno',
'and',
('tacos', 'tamales', 'and', 'salsa'),
('tacos', 'tamales', 'and', 'jalapeno', 'salsa')),
('e',
'd',
('a', 'b', 'c', 'd', 'f', 'g', 'h'),
('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h')))
for new, old, lat, expected in test_cases:
result = insertR(new, old, lat)
assert result == expected
def insertR(new, old, lat):
return (() if isnull(lat)
else cons(car(lat),
cons(new, cdr(lat)) if iseq(old, car(lat))
else insertR(new, old, cdr(lat))))
Just as the other functions, we start by defining the exit condition. Also since we are dealing with lists here, we always return an empty list, to be a part of cons at the end of execution. Then things start to get complicated. However, as we are always going to insert a new element to the right of the found element, we would then construct a new lat, with the same car value.
Next, the cdr of the new list, is defined by checking if the car value is equal to the old function parameter. If it is the case, we construct a new list as the cdr of original. This new list will have new function parameter as the car, and the cdr being the second parameter of the cons call.
However, if the check is failed, we recurse the insertR function with cdr of original lat. Also notice, just like rember, we are only doing this once, for now.
Next, we try insertL
def test_insertL():
test_cases = (('topping',
'fudge',
('ice', 'cream', 'with', 'fudge', 'for', 'dessert'),
('ice', 'cream', 'with', 'topping', 'fudge', 'for', 'dessert')),
('jalapeno',
'and',
('tacos', 'tamales', 'and', 'salsa'),
('tacos', 'tamales', 'jalapeno', 'and', 'salsa')),
('e',
'd',
('a', 'b', 'c', 'd', 'f', 'g', 'h'),
('a', 'b', 'c', 'e', 'd', 'f', 'g', 'h')))
for new, old, lat, expected in test_cases:
result = insertL(new, old, lat)
assert result == expected
def insertL(new, old, lat):
return (() if isnull(lat)
else cons(new, lat) if iseq(car(lat), old)
else cons(car(lat), insertL(new, old, cdr(lat))))
While it should be similar to insertR, but the code looks much simpler. First of everything we have the exit condition, as usual. Then we check if the car of the given lat is equal to the given old parameter. Considering we are now inserting new element to the left of matched atom, we just need to construct the new list by putting new parameter as car, and the original lat as cdr.
However, if there’s no match, we send the cdr of original lat to insertL again, then construct the new list by combining it with the car of original lat.
Next we have substitution, which is the subst function. Instead of removing, or inserting a new element, we substitute an atom with another from a given lat.
def test_subst():
test_cases = (('topping',
'fudge',
('ice', 'cream', 'with', 'fudge', 'for', 'dessert'),
('ice', 'cream', 'with', 'topping', 'for', 'dessert')),
('jalapeno',
'and',
('tacos', 'tamales', 'and', 'salsa'),
('tacos', 'tamales', 'jalapeno', 'salsa')),
('e',
'd',
('a', 'b', 'c', 'd', 'f', 'g', 'h'),
('a', 'b', 'c', 'e', 'f', 'g', 'h')))
for new, old, lat, expected in test_cases:
result = subst(new, old, lat)
assert result == expected
def subst(new, old, lat):
assert isatom(new) and isatom(old) and islat(lat)
return (() if isnull(lat)
else cons(new, cdr(lat)) if iseq(old, car(lat))
else cons(car(lat), subst(new, old, cdr(lat))))
Skipping the exit condition, as it is always the same in this chapter. If we are observing close enough subst looks very similar to insertL. The only difference happens only when the car of lat matches the old parameter. This time, the second parameter to cons, is the cdr of original list, i.e. original list without the car element.
Then we have subst2, which does replace for either one of two cases.
def test_subst2():
test_cases = (('vanilla',
'chocolate',
'banana',
('banana', 'ice', 'cream', 'with', 'chocolate', 'topping'),
('vanilla', 'ice', 'cream', 'with', 'chocolate', 'topping')), )
for new, o1, o2, lat, expected in test_cases:
result = subst2(new, o1, o2, lat)
assert result == expected
def subst2(new, o1, o2, lat):
return (() if isnull(lat)
else cons(new, cdr(lat)) if or_(iseq(o1, car(lat)), iseq(o2, car(lat)))
else cons(car(lat), subst(new, o1, o2, cdr(lat))))
Nothing really new here, except we have a boolean OR operation here to handle the ‘either .. or ..’ case here.
Next, we shall look at how each of the functions above construct a new list (without excessive car and cdr calls for clarity).
# Given these parameters
lat = ('lorem', 'ipsum', 'dolor', 'sit')
old, old2 = 'ipsum', 'amet'
new = 'meow'
# rember: remove an element
print(cons(lat[0],
cons(lat[2],
cons(lat[3],
())))) # prints ('lorem', 'dolor', 'sit')
# insertR: insert a new atom to the right of the matched atom
print(cons(lat[0],
cons(lat[1],
cons('meow',
lat[2:])))) # prints ('lorem', 'ipsum', 'meow', 'dolor', 'sit')
# insertL: insert a new atom to the left of the matched atom
print(cons(lat[0],
cons('meow',
lat[1:]))) # prints ('lorem', 'meow', 'ipsum', 'dolor', 'sit')
# subst/subst2: substitute the matched atom with a new atom
print(cons(lat[0],
cons('meow',
lat[2:]))) # prints ('lorem', 'meow', 'dolor', 'sit')
However, chances are we may want the functions to apply the operations multiple times. So instead of removing only the first member, we can expand rember into multirember as follows:
def test_multirember():
test_cases = (('cup',
('coffee', 'cup', 'tea', 'cup', 'and', 'hick', 'cup'),
('coffee', 'tea', 'and', 'hick')),)
for a, lat, expected in test_cases:
result = multirember(a, lat)
assert result == expected
def multirember(a, lat):
return (() if isnull(lat)
else multirember(a, cdr(lat)) if iseq(a, car(lat))
else cons(car(lat), multirember(a, cdr(lat))))
Practically nothing much is changed. Except the function call at the end is changed (because the function name itself is changed), the only notable change happens only when a matching atom is found. Instead of returning the cdr and call it a day, we recurse the function with the cdr of original lat.
Then we move on to multiinsertR,
def test_multiinsertR():
test_cases = (('fried',
'fish',
('chips', 'and', 'fish', 'or', 'fish', 'and', 'fried'),
('chips', 'and', 'fish', 'fried', 'or', 'fish', 'fried', 'and', 'fried')),)
for new, old, lat, expected in test_cases:
result = multiinsertR(new, old, lat)
assert result == expected
def multiinsertR(new, old, lat):
return (() if isnull(lat)
else cons(car(lat),
cons(new, multiinsertR(new, old, cdr(lat))) if iseq(old, car(lat))
else multiinsertR(new, old, cdr(lat))))
It is very similar to the original insertR. The only difference compared to the original again happens when a match is found. Instead of passing the cdr to the second argument of the nested cons, we send it for recursion.
Next we have multiinsertL,
def test_multiinsertL():
test_cases = (('fried',
'fish',
('chips', 'and', 'fish', 'or', 'fish', 'and', 'fried'),
('chips', 'and', 'fried', 'fish', 'or', 'fried', 'fish', 'and', 'fried')),)
for new, old, lat, expected in test_cases:
result = multiinsertL(new, old, lat)
assert result == expected
def multiinsertL(new, old, lat):
return (() if isnull(lat)
else cons(new, cons(old, multiinsertL(new, old, cdr(lat)))) if iseq(old, car(lat))
else cons(car(lat), multiinsertL(new, old, cdr(lat))))
However, it is not so simple in multiinsertL. Firstly when a match happens, compared to the original insertL we do not have the cdr of original lat to deal with. Recursing the function with original lat naïvely will result in a infinite loop. So the proper way to do this is to firstly break the lat into cat and cdr pair. Then throw the cdr for recursion, before combining its result with the original cat with cons.
Last but not least, the multisubst function,
def test_multisubst():
test_cases = (('fried',
'fish',
('chips', 'and', 'fish', 'or', 'fish', 'and', 'fried'),
('chips', 'and', 'fried', 'or', 'fried', 'and', 'fried')),)
for new, old, lat, expected in test_cases:
result = multisubst(new, old, lat)
assert result == expected
def multisubst(new, old, lat):
return (() if isnull(lat)
else cons(new, multisubst(new, old, cdr(lat))) if iseq(old, car(lat))
else cons(car(lat), multisubst(new, old, cdr(lat))))
Compared to the original subst function, there’s no much change here. The cdr call in the matching case is replaced with the recursive call. However, if we read the code again carefully, the second part of the cons calls for either matching or not matching case are both identical. Therefore we can rewrite the function as follows for clarity
def multisubst(new, old, lat):
return (() if isnull(lat)
else cons(new if iseq(old, car(lat)) else car(lat),
multisubst(new, old, cdr(lat))))
So this concludes the chapter for 1 dimensional list manipulation through recursion.
