List traversal baby steps
For traversing lists using recursion, there's only 3 things that matter
- the empty list - always check if your list is empty before anything!
- the head of the list – the first item
- the tail of the list – the entire list except the first item
Ok, and here's the functions we'll use to write our programs
def is_empty (ls):
return ls == []
def head (ls):
return ls[0]
def tail (ls):
return ls[1:]
Usage of the functions is straightforward
is_empty ([]) # => True
is_empty ([ 1, 2, 3 ]) # => False
head ([ 1, 2, 3 ]) # => 1
tail ([ 1, 2, 3 ]) # => [2,3]
Ok, so let's write our list_sum function – I think you'll agree that we ended up with a very readable program thanks to the list helpers we defined
def list_sum (ls):
if is_empty (ls):
return 0
else:
return head (ls) + list_sum (tail (ls))
print (list_sum ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 28
But you tagged this with tail recursion, so with the help of an optional parameter and a default value, we can move the recursive call into tail position. Changes in bold
def list_sum (ls, acc = 0):
if is_empty (ls):
return acc
else:
return list_sum (tail (ls), head (ls) + acc)
print (list_sum ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 28
But Python doesn't really have tail-call elimination, so you'd still have to do something else to ensure stack-safety.
Smoke higher-order functions every day
Using head and tail relieved us from the tedium (and ugliness) of [0] and [1:], but this pattern of list traversal is so common that we can relieve ourselves from even thinking at this level altogether!
Let's look back at our function, list_sum. This function traverses a list and performs addition using the built-in + function. What if instead of + we wanted to multiply all the elements using *?
def list_sum (ls):
if is_empty (ls):
return 0
else:
return head (ls) + list_sum (tail (ls))
def list_product (ls):
if is_empty (ls):
return 1
else:
return head (ls) * list_product (tail (ls))
print (list_product ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 5040
The only thing that's different is 0 changed to 1 and + changed to *. We don't want to rewrite all of that each time we want to do something with a list. If we abstract those values using function parameters, we can capture the very essence of list traversal in this nice little program
from operator import add, mul
def list_reduce (f, acc, ls):
if is_empty (ls):
return acc
else:
return list_reduce (f, f (acc, head (ls)), tail (ls))
def list_sum (ls):
return list_reduce (add, 0, ls)
def list_product (ls):
return list_reduce (mul, 1, ls)
print (list_sum ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 28
print (list_product ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 5040
And higher-order functions can be built using other higher-order functions. Then before you know it, you're doing all sorts of high-level transformations and traversals!
Notice how we're not thinking about head or tail at this point. Hard-on-brain things like not [], ls[0] and ls[1:] are out-of-sight and consequently out-of-mind.
def map (f, ls):
return list_reduce (lambda acc, x: acc + [ f (x) ], [], ls)
def square (x):
return x * x
print (map (square, [ 1, 2, 3, 4, 5, 6, 7 ]))
# => [1, 4, 9, 16, 25, 36, 49]
