Functional Programming Review

When I left college and landed my first job as a C++ developer I read the [Pragmatic Programmer] by Andy Hunt and Dave Thomas.

The book is great and I highly recommend it. It helped me make the transition from classroom to working developer. One piece of advice that the book gives that has stuck with me is to always be learning new languages. Don’t think of your self as a X developer. Rather, view programming languages as models for how to solve problems.

I took that to heart and for several years I attempted to learn a new language every year. Fast forward 20+ years and that philosophy has served me well. I don’t learn a new language a year any more (cause I don’t have that kind of time) but I still try to explore unfamiliar language features, how they’re designed, and the nuances of their strengths and weaknesses.

In 2014 I learned Scala and have delivered a few projects with it. At the time I found the learning curve for Scala to be similar to C++. I didn’t find the syntax to be particularly complicated but the type system and the functional programming concepts had me scratching my head.

I put in the time required and eventually I become productive with the language. These days I don’t use Scala (or Java for that matter) very often. I tend to reach for Node.js or Python depending on what I’m trying to do. While Scala hasn’t stuck with me, the concepts I learned while working with it have.

The functional programming toolbox is a powerful one. My only quibble with it is the mathematically based naming conventions. If I don’t use techniques like monad, monoid, functors, and so on, on a daily basis I completely forget what they are. So I find myself crawling the web and looking at Haskell tutorials trying to remember the functional jargon.

That’s why I’m writing this little post. I want a cheat sheet. Of course, there are many of these online already but I’m hoping that by going through the exercise of writing it all down the knowledge will stick in my head.

A Few Disclaimers#

None of the below ideas are mine. I’ve assembled the below summary based on the work of others. The resources that most heavily influenced this post are:

• Typeclassopedia from the Haskell Wiki.
• Scott Wlaschin’s excellent The Functional Programmer’s Toolkit talk and his lecture on Railway Oriented Programming.
• Mark Seemann’s blog post Better Abstractions Revisited
• Miklos Martin’s blog post Monad Laws for Regular Developers
• The crowd sourced Professor Fisby’s Mostly Adequate Guide to Functional Programming
• Fabian Beuke’s blog post Monads in Python
• The source code from the returns framework.

The Functional Programming Toolbox#

Thinking about Functions#

Higher Order Functions#

A higher order function is simply a function that does one or both of the following.

1. It takes another function as a parameter.
2. It returns a function as it’s result.

Higher order functions are the basic building blocks of FP.

Pure Functions#

A function is called a pure function if it produces no side effects.

A side effect is:

• Modifying a variable.
• Modifying a data structure in place.
• Reading from or writing to a file.
• Reading or writing to a database.

For example:

nums = [0,1,2,3,4,5,6,7,8,9]

# Count is a pure function. It doesn't change the list.
nums.count(2)
# Outputs 1

# Pop is not a pure function. It changes the list.
nums.pop()
# Returns 9.
# Now the list is [0,1,2,3,4,5,6,7,8]

Closures#

A closure is simply a nested function that is bound with a piece of data.

# Demonstrate a closure.
def provide_counter() -> Tuple[Callable, Callable]:
  _counter_value: int = 0

  # _increment is a closure.
  def _increment():
    nonlocal _counter_value
    _counter_value += 1
    return _counter_value

  # _current_value is also a closure.
  def _current_value():
    nonlocal _counter_value
    return _counter_value
  
  return _increment, _current_value

increment, current_value =  provide_counter()

increment()
increment()
increment()

print(current_value())
# outputs 3

Currying#

Currying is way to transform a multiple-argument function into a single argument function by evaluating incremental nesting of function arguments.

It transforms a function signature like this: f(a,b,c) to f(a)(b)(c)

# A typical add function
def add(a:int, b:int) -> int:
  return a + b

This is used like:
sum = add(1,2)

But if we want to add more than 2 values we have to call add multiple times. Such as:
sum = add(add(1,2),3)

A limited curried version of add.

def add(a):
  def _add(b):
    return a + b
  return _add

Using the curried version of add. sum = add(1)(2)

We can use a decorator to simplify currying.

# Define a decorator for making curried functions.
from functools import partial, wraps
from inspect import signature

def curry(func):
  @wraps(func)
  def _curry(param):
    if len(signature(func).parameters) == 1:
      return func(param)
    return curry(partial(func, param))
  return _curry

# Use the decorator.
@curry
def add(a:int, b:int, c:int) -> int:
  return a + b + c

# Use the function
add(1)(2)(3)

Currying is useful when composing and chaining functions.

Composition#

Function composition is building larger functions out of smaller ones.

We can use the reduce function in functools to compose functions. Note: StackOverflow demonstrates a range of ways to implement this

# First define a compose function to enable building functions
# out of functions.
from functools import reduce
from typing import Callable, List

# The identify function just returns the input provided.
identity = lambda i:i

# Define a compose function that enables  easily converting 
# compose(a,b,c) to a(b(c())).
def compose(*functions: Callable) -> Callable:
  def _apply(f, g):
    return lambda x: f(g(x))
  return reduce(_apply, functions, identity)

With our shiny new compose function we can now create new functions out of composing smaller ones.

double = lambda i:i*2
triple = lambda i:i*3
quadruple = lambda i:i*4

do_all_the_things = compose(double, triple, quadruple)
result = do_all_the_things(2)
# Result = 48
assert do_all_the_things(2) == quadruple(triple(double(2)))

Chaining#

Composition is handy, but often what I want is compose(a, b,c) to orchestrate a() -> b(output of a) -> c(output of b).

We could just specify the reverse order using the compose function.

step_1 = lambda i : print('Step 1')
step_2 = lambda i : print('Step 2')
step_3 = lambda i : print('Step 3')

expected_steps = compose(step_3,step_2,step_1) 
# same as calling c(b(a()))

expected_steps(None)
# Prints Step 1, Step 2, Step 3

This works but is unintuitive. Here is a simple chain method to do what I want.

from typing import Callable

def chain(*functions: Callable) -> Callable:
  """Given chain(a,b,c) orchestrates a() -> b(output of a) -> c(output of b)"""
  def _chain(input):
    accumulate_result = input
    for func in functions:
      accumulate_result = func(accumulate_result)
    return accumulate_result
  return _chain

We can use this to chain functions to feed the output of a function down the chain.

double = lambda i:i*2
triple = lambda i:i*3
quadruple = lambda i:i*4

do_all_the_things = chain(double, triple, quadruple)

result = do_all_the_things(2)
# Result is 48

assert chain(double, triple, quadruple)(2) == quadruple(triple(double(2)))

FP Philosophy#

I think of functional programming as prioritizing the following principles.

Functions are are the building blocks in which everything is expressed. With regards to functions:

• Design functions that do one thing well.
• Design functions that work together (composability).
• Design functions that do not mutate state (pure functions, immutable data).

Type systems are front and center in functional programming. Using a type checker reduces the likelihood for errors. I find that when I’m doing functional programming I tend to spend more time fussing with the type checker than I do any thing else.

FP Jargon#

I find the jargon in functional programming complicates the entire experience. Here are the main terms.

FP Tools#

Not surprisingly, the number one tool in the functional programmer’s toolbox is functions. Here are the most common functions that get implemented to achieve some type of programmatic behavior.

Functional Operations#

The below table is a list of operative functions that we can define to work on data in a functional way.

WTF is a Monoid?#

A monoid is just a function that adheres to a set of rules. They are useful when you need to entities (e.g. addition, concatenating strings).

Monoid Rules A monoid formally adheres to the following rules.

1. The Closure Rule: The result of combining two things is always another one of those things (i.e. the output of a monoid has the same type as the inputs.).
2. The Associative Rule: When combining more than two things, which pairwise combination you do first doesn’t matter. Consider the associative rule of addition.
   (1 + 2) + 3 == 1 + (2 + 3)
3. Identity Element: There is a special thing called zero such that when you combine any thing with zero you get the original thing back. For example: 1 + 0 = 1 “Dog” + "" = “Dog

The below snippet demonstrates the three rules.

# The Closure Rule Example.
# Pairwise operations that work on series of elements.
from functools import reduce
reduce(lambda a,b: a + b, [1,2,3,4])

# The Associative Rule
# The work can be divided, computed in parallel steps, and 
# incremental accumulation.
from itertools import accumulate
list(accumulate([1,2,3,4], lambda a,b: a+b))

# The Identity Element Rule
# Initial value for empty or missing data.
reduce(lambda a,b: a + b, [1,2,0,3,0,0,4,0,0,0])

A common challenge in FP is converting things that do not behave like monoids into something that does. We use the map function to do this.

For example you could map the Customer class to a numerical value of customer stats. Then leverage the reduce function to calculate some aggregation (sum, min, max, etc) on the customers.

Several established design patterns behave like monoids.
For example:

• Composite Pattern
• Null Object Pattern
• Composable Commands
• Closure of Operations

When designing functions, keep in mind that a function is only a monoid if it adheres to all three rules. Behaviors that make a function NOT a monoid are:

• Not pairwise (i.e. operating on parameters that are less or more than two or of different types.)
• The output is a different type than the input.
• Cannot deal with empty values.

WTF is an Effect?#

An effect is simply a generic type. In Python effects are implemented with classes and named tuples.

Reconciling between Pure Types and Effects
In FP land it’s bad form to ping pong between primitives (int, str, bool) and effects (List[int], Option[bool]).

The convention is to use a map function to convert between primitives and effects and from effect to a different effect.

# Convert a list of time samples in MS to seconds.
list(map(lambda i: i/1000, [1242, 1783, 430]))

In FP land an effect with a map function is referred to as a functor. So, let’s look at functors.

WTF is a Functor?#

Per Wikipedia, a functor is a design pattern that enables applying functions to a value inside of a generic type without changing the structure of the generic type.

A functor has the following properties.

1. It is an effect type (i.e. a generic type).
2. It has a map function that applies a function to the effects world.
3. It adheres to the Functor Laws which ensures that the map function does not change the structure of the container only the elements. Simply put, map changes a value without altering it’s context.

Functor Law: Identity#

Mapping the identity function over every item in a container has no effect.

Functor Law: Composition#

Mapping a composition of two functions over every item in a container is the same as first mapping one function, and then mapping the second one.

Functor Example#

Here is an example of creating a generic List functor in Python.

from __future__ import annotations

from collections import UserList
from typing import Callable, Generic, TypeVar
A = TypeVar('A')
B = TypeVar('B')

class MyList(UserList, Generic[A]):
  def __init_subclass__(cls) -> None:
    return super().__init_subclass__()
  
  def map(self, func: Callable[[A], B]) -> MyList[B]:
    return MyList(list(map(func, self.data)))

some_ints: MyList[int] = MyList([1,2,3,4])
squared_values: MyList[int] = some_ints.map(lambda i: i*i)
print(squared_values)
# [1, 4, 9, 16]

Chaining Functions across Effects#

In our programs imagine there are two worlds. One world is the land of primitives (str, int, bool). The other world is the land of effects (abstract data types, e.g. Dollars, Seconds).

A world changing function is one that takes a primitive and returns an effect (i.e. generic type).

The bind function enables composing mismatched functions. This enables removing nested conditionals.

# Bind function are effect specific. 
# Here is one for a simple Maybe class
from __future__ import annotations

from typing import Callable, Generic, TypeVar
A = TypeVar('A')

class Maybe(Generic[A]):
  def __init__(self, value: A | None) -> None:
    self._value = value

  def unwrap(self) -> A:
    return self._value

  def has(self) -> bool:
    return self._value is not None

  def bind(self, next_func: Callable[[A], Maybe[A]]) -> Maybe:
    if self.has():
      return next_func(self.unwrap())
    else:
      return Maybe(None)

We can use bind to chain options.

a = Maybe[int](5)
result = a.bind(lambda x: Maybe(x + 10)) \
  .bind(lambda x: Maybe(x/2)) \
  .bind(lambda x: Maybe(x * x))

WTF is a Monad?#

Monads are classes that enable chaining effect generating functions in a series.

A Monad is:

• An effect type (i.e. A generic type.).
• That has a return function that takes a primitive type and returns it wrapped in an instance of the monad. This is “lifting” the primitive into the effect’s world. This could be named return, pure, wrap, unit, whatever.
• That has a bind function that enables chaining functions in the effect world. This is commonly named bind, fmap, or flat_map.
• The bind and return functions must adhere to the Monad Laws.

A word about Operators
Operators are things like (+,-,*, /). They have a left side and a right side. Take this expression for example. A + B

The ‘+’ is an operator. A is on the left side of the operator while B is on the right side of the operator.

Monad Law: Left Identity#

If an item on the left of an operator doesn’t change the item on the right, it is said to adhere to the left identity law.

# 
from __future__ import annotations

from typing import cast, Callable, Generic, TypeVar
A = TypeVar('A')

# Let's define a Just Monad. I
class Just(Generic[A]):
  def __init__(self, value: A) -> None:
    self._value = value

  def unwrap(self) -> A:
    return self._value

  def return(self, value: A) -> Just[A]:
    return Just(value)

  def bind(self, next_func: Callable[[A], Just[A]]) -> Just[A]:
    return next_func(self.unwrap())

  def __eq__(self, other: object) -> bool:
    """Enable directly comparing two Just instances."""
    if isinstance(other, Just):
      return self._value.__eq__(cast(Just, other.unwrap()))
    else:
      raise Exception('Can only compare a Just to a Just.')

value = 1
double = lambda i: Just(i * 2)

Just(value).bind(double) == double(value)

Monad Law: Right Identity#

If wrapping your monad with the same monad type does not change its value, then it is said to adhere to the right identity law.

# Using the above definition of Just, we see that wrapping 
# Just with a Just doesn't change it's value.
Just(5).bind(lambda i: Just(i)) == Just(5)

Monad Law: Associativity#

If the order nesting of functions on a container doesn’t matter then the class is said to adhere to the associativity law.

# Using the above definition of Just.
square = lambda i: Just(i * i)
by_four = lambda i: Just(i * 4)
Just(5).bind(lambda i: square(i).bind(by_four)) == Just(5).bind(lambda i: square(i).bind(by_four))

WTF are Applicatives?#

We can combine effects in parallel using applicative functors.

An applicative functor has the following characteristics:

1. It is an effect type.
2. It has a pure function.
3. It has a function that combines two effects into one. This is typically called ap, apply, or pair.
4. It must adhere to the Applicative Functor Laws. Note: See the definition of applicatives in the return framework for Python examples of the laws.

In the earlier section on pure functions, we established that a pure function is one that doesn’t produce any side effects.

In functional programming the word pure pulls double duty. There are pure functions and there is also the pure function.

The pure function is like return on a monad. It takes a parameter “a” and returns F(a). To state this plainly, pure takes a value and wraps it in an effect class (think container).

Here is a definition of a simple effect with a pure function.

from __future__ import annotations
from typing import Generic, TypeVar
A = TypeVar('A')

# Define an effect with a pure function on it.
class AnEffect(Generic[A]):
  def __init__(self, value: A):
    self._value = value

  def pure(self, value: A) -> AnEffect[A]:
    return AnEffect(value)

# Using the pure function to create new effects 
# from "pure" values.
a = AnEffect[int](1234)
b = a.pure(5678)

In addition to the pure function, Applicative Functors (AF) have an apply function. The apply function enables an AF to apply a series of functions to its values.

The traditional use of Applicative Functors is to define containers (e.g. Lists, Sets, Trees).

Earlier, when we created a functor example We extended the Python definition of List to behave like a Functor. Let’s do that again but this time let’s make a List that works like an Applicative Functor.

# Enhance List to behave as an AF.
from __future__ import annotations

from collections import UserList
from typing import Callable, Generic, List, TypeVar
A = TypeVar('A')
B = TypeVar('B')

class MyAFList(UserList, Generic[A]):
  def __init_subclass__(cls) -> None:
    return super().__init_subclass__()
  
  def pure(self, value: List[A]) -> MyAFList[A]:
    return MyAFList(value)

  def apply(self, funcs: List[Callable]) -> ApplicativeList[B]:
    # For each value this MyAFList, call it with every function 
    # in the functions list.
    pure_list = [f(value) for f in funcs for value in self.data]

    # Wrap the results in a MyAFList.
    return MyAFList(pure_list)

a = MyAFList([0, 1,2,3,4,5,6,7,8,9])
a.apply([lambda i: i*i])
# [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

It may not be clear how the way calling apply can affect the end result. Notice the different behavior in calling apply once with multiple functions vs calling apply once for each function.

square = lambda i: i*i
add_two = lambda i: i+2
divide_by_2 = lambda i: i/2

b = MyAFList([0,1,2,3])
# Preserve the value of each step.
b.apply([square, add_two, divide_by_2])
# [0, 1, 4, 9, 2, 3, 4, 5, 0.0, 0.5, 1.0, 1.5]

# Accumulate the application of the functions.
b.apply([square]).apply([add_two]).apply([divide_by_2])
# [1.0, 1.5, 3.0, 5.5]

Is that it?#

Did I cover every aspect of functional programming? No, not even close. I wanted an article that I can reread anytime I need to pick up the FP toolbox and now I’ve got one.

In the future I may expand this to include topics that I just don’t have the energy to tackle right now. For example, I’d like to include the Haskell concepts Foldable, Traversable, Bifunctor, Category, Arrow, and Comonad but that will have to wait for now.

Until next time…

• Sam