## (note (code cslai))

Notes on codes, projects and everything

# The Little Pythoner, Part 3

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,
cons(lat,
cons(lat,
())))) # prints ('lorem', 'dolor', 'sit')

# insertR: insert a new atom to the right of the matched atom
print(cons(lat,
cons(lat,
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,
cons('meow',
lat[1:]))) # prints ('lorem', 'meow', 'ipsum', 'dolor', 'sit')

# subst/subst2: substitute the matched atom with a new atom
print(cons(lat,
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. 