# Composing Programs



## Higher Order Functions

The book gives examples of similar functions that perform summation. It then shows a basic template:

   def <name>(n):
total, k = 0, 1
while k <= n:
total, k = total + <term>(k), k + 1


Here's a full example:

def summation(n, term):
total, k = 0, 1
while k <= n:
total, k = total + term(k), k + 1

def cube(x):
return x * x * x

def sum_cubes(n):
return summation(n, cube)

result = sum_cubes(3)

Or call summation() directly:

summation(10, square)

You can also use an identity function to sum natural numbers:

def identity(x):
return x

def sum_naturals(n):
return summation(n, identity)

Another, less-clever way to write it that might clarify things:

def summation(n, fn):
total = 0
k = 1

while k <= n:
total = total + fn(k) # summation
k = k + 1 # increment
return total

## Recursive Functions

Nice trick:

# Get last digit
12345 % 10 # 5

# Get all but last digit
12345 // 10 # 1234

Recursion example:

def sum_digits(n):
"""Return the sum of the digits of positive integer n."""
if n < 10:
return n
else:
all_but_last, last = n // 10, n % 10
return sum_digits(all_but_last) + last

### Iteration vs. Recursion

Factorial examples in Python:

def fact_iter(n):
total, k = 1, 1
while k <= n:
total, k = total * k, k + 1

def fact(n):
if n == 1:
return 1
else:
return n * fact(n-1)

### Mutual Recursion

def is_even(n):
if n == 0:
return True
else:
return is_odd(n-1)

def is_odd(n):
if n == 0:
return False
else:
return is_even(n-1)

result = is_even(4)

Or:

def is_even(n):
if n == 0:
return True
else:
if (n-1) == 0:
return False
else:
return is_even((n-1)-1)

Here's an example with a game:

def play_alice(n):
if n == 0:
print("Bob wins!")
else:
play_bob(n-1)

def play_bob(n):
if n == 0:
print("Alice wins!")
elif is_even(n):
play_alice(n-2)
else:
play_alice(n-1)

### Printing Recursion

def cascade(n):
if n < 10:
print(n)
else:
print(n)
print(n)

Results:

>>> cascade(123456)
123456
12345
1234
123
12
1
12
123
1234
12345
123456

### Tree Recursion

This is when a function makes multiple calls to itself. Fibonacci example:

def fib(n):
if n == 1:
return 0
if n == 2:
return 1
else:
return fib(n-2) + fib(n-1)

## Data Abstraction

Accessing pairs:

pair = [10, 20]
x, y = pair # x=10, y=20

Or:

from operator import getitem
getitem(pair, 0)
getitem(pair, 1)

The rational number example:

from fractions import gcd

nx, dx = numer(x), denom(x)
ny, dy = numer(y), denom(y)
return rational(nx * dx + ny * dx, dx * dy)

def mul_rationals(x, y):
return rational(numer(x) * numer(y), denom(x) * denom(y))

def print_rational(x):
print(numer(x), '/', denom(x))

def rationals_are_equal(x, y):
return numer(x) * denom(y) == numer(y) * denom(x)

def rational(n, d):
g = gcd(n, d)
return [n//g, d//g]

def numer(x):
return x[0]

def denom(x):
return x[1]

You can then do:

half = rational(1, 2)
print_rational(half)
third = rational(1, 3)
print_rational(mul_rationals(half, third))
print_rational(add_rationals(third, third))

### Abstraction Barriers

Use higher level functions when possible.

Do this:

# This doesn't assume anything about the way rationals are created
def square_rational(x):
return mul_rational(x, x)

def square_rational_violating_once(x):
return rational(numer(x) * numer(x), denom(x) * denom(x))

or this:

def square_rational_violating_twice(x):
return [x[0] * x[0], x[1] * x[1]]

Or create your own data type with functions instead of using lists to represent the pairs:

def pair(x, y):
"""Return a function that represents a pair."""
def get(index):
if index == 0:
return x
elif index == 1:
return y
return get

def select(p, i):
"""Return the element at index i of pair p."""
return p(i)