Lists that shrink

A function can call itself. That is how a Lisp walks a list, and it is the idea this language family is built on.

Another kind of list

What is '(apple pear plum)?

A list of three names. The single quote in front says: keep this group as it is, do not call apple.

>>> '(apple pear plum)
(apple pear plum)

This is the older kind of list, the one Lisp is named for. Chapter 7’s #[...] is the everyday kind; this kind is the one that shrinks.

How do we get the first item?

car:

>>> (car '(apple pear plum))
apple

And everything after the first?

cdr, which is the rest of the list, itself a list:

>>> (cdr '(apple pear plum))
(pear plum)

The names are old and odd. Read car as “the first” and cdr as “the rest”.

What is the rest of '(plum)?

The empty list, written nil or '(). nil? asks whether a list is empty:

>>> (cdr '(plum))
()
>>> (nil? (cdr '(plum)))
True

How do we put an item on the front?

cons:

>>> (cons 'fig '(apple pear))
(fig apple pear)

Counting by shrinking

How long is '(apple pear plum)?

One more than the length of its rest, '(pear plum).

How long is '(pear plum)?

One more than the length of '(plum).

How long is '(plum)?

One more than the length of '().

And how long is '()?

Zero. This is the only question that has a plain answer, so it is the one to ask first.

Can we write that as a function?

Ask the plain question first, and otherwise ask the same question of the rest:

def length [items]:
  if (nil? items):
    0
  else:
    (+ 1 (length (cdr items)))

print (length '(apple pear plum))

That prints 3. length calls itself on a shorter list each time, until the list is empty.

The shrinking rule

Ask nil? first. Otherwise, do something with the car and call yourself on the cdr.

Looking for something

Is 'pear in '(apple pear plum)?

Ask nil? first: no, the list is not empty. Is 'pear the car? No, that is 'apple. So ask the same of the rest.

Is 'pear in '(pear plum)?

Not empty; the car is 'pear. Yes.

Write it.

def member? [item items]:
  if (nil? items):
    False
  elif (== item (car items)):
    True
  else:
    (member? item (cdr items))

print (member? 'pear '(apple pear plum))
print (member? 'kiwi '(apple pear plum))

True, then False. Names that ask a question end in ? by custom.

Building a new list

How do we take 'pear out of '(apple pear plum)?

Ask nil? first: an empty list with nothing removed is still empty. If the car is the item, the answer is the rest. Otherwise keep the car and remove the item from the rest:

def remove [item items]:
  if (nil? items):
    nil
  elif (== item (car items)):
    (cdr items)
  else:
    (cons (car items) (remove item (cdr items)))

print (remove 'pear '(apple pear plum))

(apple plum). The cons puts each kept item back on the front of the answer for the rest.

Why keep two kinds of list?

#[...] lists are Python’s, and every Python library speaks them. The quoted kind is what Koskari itself is written in: a program is a list of lists, and the functions in this chapter are how the language reads its own source. Use #[...] for data and this kind when a problem is one item and the rest.