*scratch*

vijay's weblog

Functional Python

Reading the Turing Award lecture(pdf) by John Backus. This is probably one of the most accessible introductions to functional programming.

Did some FP exercises in Python:

# function is defined as inner_product:
# [a,b,c] * [x,y,z] = [(a * x) + (b * y) + (c * z)]
def inner_product(x, y): return reduce(add, map(mult, zip(x, y)))

# where mult and add are defined as:
def mult(x): return x[0] * x[1]
def add(x, y): return x + y
# in a FP language, + and * are first-class functions, so we don't
# need to specially def them.

#test
>>> inner_product([1, 2, 3], [6, 5, 4])
28

Contrast this with the imperative equivalent, where we have to say how to do it, not what to do:

def inner_product(x, y):
  c = 0
  n = len(x)
  for i in range(n):
      c = c + x[i] * y[i]
  return c

The imperative inner_product operates on “state” and one should mentally execute the code to understand it. In contrast, the functional version specifies how we want to transform the data to produce an expected result. This is closer to how we visualize the solution for a given problem. For instance, consider how the FP inner_product evaluated the sample input:

  1. Transform the lists into pairs: zip([1, 2, 3], [6, 5, 4]) => [(1,6), (2, 5), (3, 4)]
  2. Multiply each pair: map(mult, [(1,6), (2, 5), (3, 4)]) => [6, 10, 12]
  3. Add the products to get the final result: reduce(add, [6, 10, 12]) => 28

Here is a function to multiply matrices, in functional style:

def matrix_mult(m, n):
    return map(lambda(e):
               map(lambda(k): reduce(add, map(mult, k)), e), # inner_product() without zip :-)
               cross_zip(m, n))

# where cross_zip is defined as:
def cross_zip(x, y):
    n = zip(*y)
    return map(lambda(e): map(lambda(k): zip(e, k), n), x)

# test
> m = [[1, 2, 3], [4, 5, 6]]
> n = [[10, 20], [30, 40], [50, 60]]
> print matrix_mult(m, n) 
[[220, 280], [490, 640]]
> m = [[0, -1, 2], [4, 11, 2]]
> n = [[3, -1], [1, 2], [6, 1]]
> print matrix_mult(m, n)
[[11, 0], [35, 20]]
> print matrix_mult(n, m)
[[-4, -14, 4], [8, 21, 6], [4, 5, 14]]
> m = [[8, 9], [5, -1]]
> n = [[-2, 3], [4, 0]]
> print matrix_mult(m, n)
[[20, 24], [-14, 15]]

Next step: redefine matrix_mult() directly in terms of inner_product() …