Learning notes on Functional Python Programming

• Book: Functional Python Programming
• Chapter: Introducing Functional Programming

Functional programming and Imperative programming

• python is an imperative programming language, which indicates which indicates the state of computation is reflected by the variables in various namespaces.

  • Like concept of "Everything is a file" in UNIX world, for imperative languages "Every state is a snapshot of variables"
  • Like the pipeline/redirection/filter concepts in UNIX, the program will always focus on states of variables, the program is nothing more then a pipeline connected filter(algorithm) collections, which may try to redirect the input data to the target output data

• python also holds some functional programming features

  • In functional programming, the states of variables were being replaced by function evaluations, each evaluation will create a new object from the current object
  • As the program is a collection of functions, it is very similar to the solving procedures in Math, we can make easy functions, then regroup them by iteration or recusion to achieve complex functions

• Comparison among different models in imperative programming: Procedural and OO

  • Procedural: procudural model will treate the data as a stream, everything will be built around the stream, the state of the program is defined by variables
  • OO: The state of the program is also determined by variables

# example Procedural
count=0
for idx in range(0,11):
    if idx % 3 == 0 or count % 5 == 0:
        count += 1

# example OO
count=0
tgtList=list()
for idx in range(0,11):
    if idx % 3 == 0 or count % 5 == 0:
        tgtList.append(idx)
sum(tgtList);

# Another OO example: a class with a method sum
class sum_list(list):
    def sum(self):
        s = 0
        for v in self.__iter__():
            s += v
        return s

• Functional Paradigm
  • To calc the sum of the multiples of 3 and 5 can be defined in two parts:
    • The sum of a sequence of numbers
    • The number for sum must pass a simple test to be selected

# A resursive sum function
def sum(sequence):
    if len(sequence) == 0:
        return 0
    return sequence[0]+sum(sequence[1:])
sum([x for x in range(1,11)]);

In the last case, the sum function is being transformed into a "divide-calc-merge" function, first divide the funtion into parts, where all parts follow a same pattern then calc it by recursion, at last merge the result at the final dest., it is a great idea to apply the resursive here.

# An impletation of function until
def until(n, filter_func, v):
    # End subject, until the bound
    if v == n:
        return []
    # If v can satisfy the selection function, then return v and check next
    if filter_func(v):
        return [v]  + until (n, filter_func, v+1)
    # If v cannot satisfy the selection function, then check next
    else:
        return until(n, filter_func, v+1)

In functional programming, it is all based on the lambda calc in math, a new keyword lambda is used to expand the area of original python.

# This usage seems like to check whether the x is belongs to a set
mult_3_5 = lambda x: x%3 == 0 or x%5 == 0
print (mult_3_5(2), mult_3_5(3))

False True

# Combine the new lambda calc with the until() function, the result is just like find the join set of the set 'lambda' and the original full set
until(11, mult_3_5, 0)

[0, 3, 5, 6, 9, 10]

Python also supports the hybrid solution to include FP into procedural programming:

print([x for x in range(0,11) if x % 3 == 0 or x %5 == 0])

[0, 3, 5, 6, 9, 10]

The last form uses Nested Generated Expressions to iterate through the collection of the vars and select the taret ones

# In python the simple orderized sum seems won't be avoided by order
import timeit
print(timeit.timeit("((([]+[1])+[2])+[3])+[4]"), timeit.timeit("[]+([1]+([2]+([3]+[4])))"))

0.3882635319896508 0.39000111201312393

Using FP flavour python to calc sqrt()

Use FP method it is very easy to generate math results

# Newton method to approach sqrt(2)
# It is also a mathematical method, convert f(x) into the lambda calc result based on x
n = 2;
def next_(n, x):
    return (x+n/x)/2
f = lambda x: next_(n, x)

a = 1.0
[round(x ,4) for x in [a, f(a), f(f(a)), f(f(f(a)))]]

[1.0, 1.5, 1.4167, 1.4142]

# A simple repeat for function f with init var a
def repeat(f, a):
    yield a
    for v in repeat(f, f(a)):
        yield v

Python is not a pure FP lanuage and the current computer arches are not LISP machines, python uses recursive method to represent the yielding of the infinite list, then we must select a iterator as the generator of the values:

# General form
# for y in some_iter: yield y;

def within(eps, iterable):
    # Check whether is satisfy the end subject or just try to iter into next
    def head_tail(eps, a, iterable):
        b = next(iterable)
        if abs(a-b) <= eps:
            return b
        return head_tail(eps, b, iterable)
    return head_tail(eps, next(iterable), iterable)

# Full sqrt function in FP:
def sqrt(a, eps, n):
    return within(eps, repeat(lambda x: next_(n, x), a))

tgt=sqrt(1.0, 0.000001, 2)
print(tgt)

1.414213562373095

Summary

This FP flavour calc of sqrt() consists of following steps:

• Define the function model to use and the iterator function
• Define the end subject of the iteration
• Iter and check the result: whether ||f(iter)-f(next_iter)|| meets the end subject

# Framework of this method:
# divide-calc-merge

#-divide
def next_(n, x):
    return (x+n/x)/2
f = lambda x: next_(n, x)

#-calc(multi times, generate f_n(a))
def repeat(f, a):
    yield a
    for v in repeat(f, f(a)):
        yield v

#-merge
def within(eps, iterable):
    # Check whether is satisfy the end subject or just try to iter into next
    def head_tail(eps, a, iterable):
        b = next(iterable)
        if abs(a-b) <= eps:
            return b
        return head_tail(eps, b, iterable)
    return head_tail(eps, next(iterable), iterable)

#-main
def sqrt(a, eps, n):
    return within(eps, repeat(lambda x: next_(n, x), a))

tgt=sqrt(1.0, 0.000001, 2)
print(tgt)

1.414213562373095