What is Functional Programming?

Functional programming is programming in a style that favours (pure) functions over other constructs.

What is a function?

• In this case, a value in Set A called x is mapped to its resultant value from Set B, f(x)
• and the value from A, 'y' is mapped to its resultant f(y)
• Set A and Set B could be anything.
• Set A could be the Set of Real Numbers, and Set B also.
• Or Set A could be the Set of possible strings, and set B the set of positive integers
• Or Set A could be the Set of 2 dimensional vectors and set B could be the Set possible lists

Example Functions

A simple function that maps a number to its square:

In Haskell:

square :: Int -> Int
square x = x * x

In Clojure:

(defn square [x]
  (* x x))

In Python:

def square(x):
    return x*x

Pure Functions

A function is pure if both:

and:

In functional programming we want to use pure functions. ie. They take values, only operate on those parameters, don't mutate state, and return a value to the caller

Pure or impure?

Map

Takes a function and a collection. Evaluates the function, passing in every item in the collection. Takes all the return values of those calls and returns them in a new collection.

map(f, coll)

[f(x) for x in coll]

{f(x):g(x) for x in coll}

{f(k):g(v) for k,v in coll.items()}

(f(x) for x in coll)

Example Map

Imperative code like this:

output = []
for word in ['this', 'is', 'a', 'list', 'of', 'words']:
    output.append(len(word))
print output

output = {}
for word in ['this', 'is', 'a', 'list', 'of', 'words']:
    output[word] = len(word)
print output

Can be expressed functionally like this:

>>> map(len, ['this', 'is', 'a', 'list', 'of', 'words'])
[4, 2, 1, 4, 2, 5]

>>> [len(word) for word in ['this', 'is', 'a', 'list', 'of', 'words']]
[4, 2, 1, 4, 2, 5]

>>> {word:len(word) for word in ['this', 'is', 'a', 'list', 'of', 'words']}
{'a': 1, 'this': 4, 'of': 2, 'is': 2, 'list': 4, 'words': 5}

Filter

Takes a collection and returns a new collection containing only those items from the first that pass some test.

filter(pred, coll)

[x for x in coll if x=='foo']

[x for x in coll if pred(x)]

{k:v for k,v in coll.items() if pred(k,v)}

Example Filter

Imperative code like this:

output = []
for word in ['this', 'is', 'a', 'list', 'of', 'words']:
    if len(word)==4:
        output.append(word)
print output

Can be expressed functionally like this:

>>> filter(lambda word: len(word)==4, ['this', 'is', 'a', 'list', 'of', 'words'])
['this', 'list']

>>> [word for word in ['this', 'is', 'a', 'list', 'of', 'words'] if len(word)==4]
['this', 'list']

Reduce

Consume all the items in a collection by passing them in turn to a function. That function gets passed the item being consumed, as well as the result of the last function call performed by reduce. In this way a collection of items are fed through a function that reduces them to one output value.

Reduce optionally takes an initial argument that will be used in the first call to the function. If this is not specified, the first call is passed two items from the start of the collection.

def func(accumulator, element):
    return ...

reduce(func, coll)

reduce(func, coll, initial_value)

fold. foldl. foldr

>>> def f(a,b):
...   print "f called with:", a, b
...   return a+b
...
>>> reduce(f, range(10))
f called with: 0 1
f called with: 1 2
f called with: 3 3
f called with: 6 4
f called with: 10 5
f called with: 15 6
f called with: 21 7
f called with: 28 8
f called with: 36 9
45

>>> def reverser(a,b):
...     print "reverser called with:", a, b
...     return [b] + a
...
>>> reduce(reverser, [1, 4, 9, 16, 25], [])
reverser called with: [] 1
reverser called with: [1] 4
reverser called with: [4, 1] 9
reverser called with: [9, 4, 1] 16
reverser called with: [16, 9, 4, 1] 25
[25, 16, 9, 4, 1]

>>> coll = [-20, 10, 100, -43, 35]
>>> reduce(lambda a,b: a if a < b else b, coll)
-43
>>> reduce(lambda a,b: a if a > b else b, coll)
100
>>> reduce(min, coll)
-43
>>> reduce(max, coll)
100
>>> min(coll)
-43
>>> max(coll)
100

Higer Order Functions

A function is said to be of a “higher order” if it takes another function as one of its aguments, or returns a function as part of it's result, or both.

Python Examples

map(function, coll)

filter(function, coll)

reduce(function, coll)

Decorators

Python decorators are functions. They get invoked during compilation and into them is passed the function that is to be decorated. They return a new function that is to replace the old one in the namespace.

def debug(fn):
    def new_func(*args, **kwargs):
        result = fn(*args, **kwargs)
        print "{} called with args: {} and kwargs: {} and returned: {}".format(fn.__name__, args, kwargs, result)
        return result
    return new_func

@debug
def solve_quadratic(a, b, c):
    sqrt_b2_minus_4ac = math.sqrt(
        b * b - 4 * a * c
    )
    return (
        (- b + sqrt_b2_minus_4ac) / (2 * a),
        (- b - sqrt_b2_minus_4ac) / (2 * a)
    )

result = solve_quadratic(10, 2, 4)

running it looks like:

$ python test.py
solve_quadratic called with args: (10, 2, -4) and kwargs: {} and returned: (0.5403124237432848, -0.7403124237432849)
result = (0.5403124237432848, -0.7403124237432849)

talk a bit about function composition?

Values

A particular magnitude, number or amount. A Precise meaning or significance.

• Values never change (immutable)
• Values can be perceived and compared to other values
• Equality and comparability are the basis for logic
• Semantically transparent
  • Don't need methods
  • I can send you values without code and you are fine
  • they are not operationally defined
  • There can't be any code overhead that is required to understand meaning, equality or comparability.
• Can be abstracted (collections)

What are values in Python?

Real numbers? yes

None? yes

Booleans? yes

Tuple? yes

Datetime? yes

String? yes

List? no

Dictionary? no

Set? no

Generator instances? no

Class instance? depends (usually no)

Class? no

Module? no

The Many Benefits of Values

Values aggregate

• Immutable collections of values are values
• All benefits apply in compositions

Composite Objects? Group a number of objects together into another.

• What properties can you ascertain about the whole?
• You start again defining the interface for the aggregate
• even with clone/copy/lock policy for each part
• Combining them you no longer have a clone/copy/lock policy
• Need a new operational interface for the aggregate
• Objects don't compose

Values can be Freely Shared

• Sharing is aliasing
• Safe
• Incremental change is cheap (persistent structures)

• Objects? Defensive copying. Locking.

Values are Easy to Fabricate

• Anything can create them easily
• Easy for tests to create
• Easy to dry run or simulate

• Object?
• You must match or emulate some kind of operational interface
• Mocks... inside mocks inside mocks

Values are Reproducible

• Stable: operations are reproducible.
• Testing
• Debugging: reproduce problems without state

• Stable: operations are reproducible means:
• Same input, same output
• Objects?
• Must establish the matching state
• Must recreate the state when the problem occured
• Global state problems
• Call a() then b() when the sun is at its zenith on tuesday

Values are Language Independent

• Any language can create values
• Any language can receive values

• examples: html, json, xml.
• Objects?
• defined by the language constructs (their methods)
• completely bound to the language of implementaion
• to break out need to code interfaces
• proxies, remotes, SOAP, REST interface generation

Values are generic

• Representations of basic values in any language
• Very small number of basic abstractions (less than 10)

• less than 10: numbers, strings, booleans, none, vectors, hashmaps, sets
• Objects? Interface is too specific. Means more and more code. Poor reuse
• how many large OOP systems can you do with less than 10 classes
• Every new thing needs a new class. Where's the reuse?
• Q: If I have a person class, and you have a person class, in their own namespaces, and they both have 'name', 'address' and 'email' what can we do with these two things?
• A: Nothing! Semantically identical. same names. completely uninteroperable.
• TOO SPECIFIC

Values make great interfaces

If your code is based on values you can:

• Move it
• Port it
• Enqueue it

• Imagine a system with component parts. What happens if you want to move one out?
• out of resources?
• another team
• another language
• Objects... you're stuck.
• In the large, we know this. We don't build objects over the wire
• we throw it all out when we program in the small

Programming with Values

Sending Values

• Reference is all you need to pass
• Cheap
• Safe and worry free

• passing a reference to a mutable thing, what information have you conveyed? Only its location
• Q: Who is the president of the United States at this point in time?
• A: The pigeon hole over there third from the left.
• Sending information with places is hard.
• Basically need to convert it to a value
• Values rule over the network. eg HTTP. Imagine an OOP protocol

Perceiving Values

• A reference is perception
• Snapshots

• How do you atomically percieve a coherent value of an object with multiple getters?
• MASSIVE concurrency problem.
• also a single threaded problem.
• Copying. Cloning. Locking. Made over and over and over again.
• basically need to create consistent values

Remembering Values

• Aliasing is remembering
• Forgetting is garbage collection

• Objects? Copy. Deep copy.

Co-ordinating Values

• No need for locks
• No need for transactions
• Concurrency FTW!

• Objects? Locks. Transactions.
• Difficult to get right. Even harder to prove it's right
• Often wrong: deadlocks, race conditions.

Locating Values

• Only one copy needed in RAM
• Memoizable
• Cachable
• Distributable