Introduction to Functional Programming Ideas
  |   Source

Functional Programming for Pythonistas

There are never-ending arguments in tech communities about things like RDBMS versus no-SQL, or functional programming (FP) versus object-oriented-programming (OOP). My goal here isn't to weigh in on that debate; those dead horses have been beaten by people far smarter than myself. These are all tools. My favorite analogy is this: If you have a giant mechanic's toolbox in front of you and you keep reaching for the crescent wrench, "you're doing it wrong." Let's open up some drawers in that toolbox and play with some different tools to see where they might be useful.

Why learn FP

This point is important, and it is difficult for me to quantify. There are lots of articles if you search "Why learn Haskell?" or "Why learn functional programming?". I believe the main benefit is that it changes how you view and approach some problems. When you encounter functional code in the wild, you will see a useful abstraction instead of a chunk of "code golf". Functional-style programming gets you to focus on the data and less about the cruft around it. It teaches you to break problems down into really small components, then glue them together to build a solution. Functional programming is heavily inspired by mathematics. Category theory has an important relationship to FP, and it seeks to abstract common patterns across "families" of objects. Don't worry, I am not going to get into those weeds in this post.

One of my favorite quotes is from the well-known network architect Russ White. He says, "If you think you've found a design with no tradeoffs, well… Guess what? You've not looked hard enough." I believe this is as applicable to network design as it is software development. When discussing programming languages and software design, time is often the tradeoff. Some of the items below can ease your cognitive burden (immutable data structures), and others require some up-front head scratching; things like thinking with types and dealing with side effects.

Why OCaml

If you are going to burn time learning something, it's best if it is useful in some capacity. When I started sipping the FP Kool-Aid, I chose to learn Haskell. All the cool kids [PhD's] are doing it! I would like to think that there is room in the automation world for a functional language. Unfortunately, I don't think Haskell is the best choice. Haskell has a steep learning curve, and it complicates common operations in a pursuit of "purity". The next contender I looked at is OCaml. It is very similar to Haskell, but it trades purity for pragmatism. Unfortunately, this is my main gripe with the language and one of Python's major shortcomings. Neither language has en explicit mechanism to signal the developer that a side-effect is occurring or that a function call might raise an exception. Despite that, there are many benefits:

  • Compiled: It's straightforward to build tiny containers from binaries.
  • REPL: utop, a great debugging tool.
  • Impure: This is a double-edged sword as mentioned previously.
    • Functions can perform side-effects (print debugging is dead simple unlike Haskell).
    • Side effects aren't forcibly bound to monads (don't worry if you don't know what that means).
  • Strongly typed
  • Good parsing libraries. Menhir, Angstrom, others.

Some other drawbacks:

  • Small community
  • Tiny library pool

Whirlwind tour

These concepts are generic to functional programming, and I will show code examples where appropriate.

Function application

In Python:

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

n = add(2, 4) # n = 6

OCaml doesn't use parenthesis for function application, although they are used to group ambiguous terms together.

let add a b = a + b

let n = add 2 4 (* val n : int = 6 *)

Immutability

In functional languages, variables are immutable by default (Rust, too!). The following code tries to create a function that takes a variable x and assign it a new value.

utop # let f x = x := x + 1;;
Line 1, characters 15-16:
Error: This expression has type 'a ref but an expression was expected of type
         int

Python lambdas have better guards (expressions only, no assignment), but "regular" functions do not. Notice that the dictionary vals is mutated by a function that doesn't return a value.

>>> vals = {"42": 42}
>>> def f(x):
...   x["42"] = 24
...
>>> f(vals)
>>> vals
{'42': 24}
>>>

Golang is just as guilty. Pointers are often used to reduce memory use, but they allow the developer to mutate values in ways that may have unexpected results.

package main

import (
    "fmt"
)

func doit(val *string) {
    *val = *val + " world!"
}

func main() {
    hello := "hello"
    doit(&hello)
    fmt.Printf("%s\n", hello)
}

hello world!

Program exited.

These are trivial pet examples, but the problem becomes clear when you look at much larger projects. It is extremely difficult to reason about the state of a program if everything is mutable and functions are allowed to create arbirary side effects.

Purity

"Pure" functions are simply those that always produce the same result given the same input. Pure functions can be written in nearly every language.

f = lambda x: x + 1

def f(x):
    return x + 1

let f x = x + 1

Think of pure functions in the same way as mathematical functions (that's where the idea originates). Addition takes two arguments and produces a result. The same result given the same input! One benefit of pure functions is that they tend to be very straightforward to test.

These are impure functions. doit above in the golang example (Play with it to see why. Hint, print the pointer address).

This function will return different values depending on what is input.

def get_input():
    return input("Type something: ")

This function might raise an exception.

def get_val(d):
    return d[42]

You may be thinking that this is a nice idea, but it's entirely useless! Exceptions happen; we need to validate inputs! This argument is correct, but few people are taught a different way to deal with the ugly "real world".

Referential transparency

This is closely related to purity. Referential transparency means that you can replace a funciton call with its return value. I'll leave this as an exercise for the reader to see why this only works with pure functions.

Higer-order functions

Thanfully, Python treats functions as first-class citizens (so does golang). This means that functions can be passed as values to other functions. Functions can also return functions (think functools.wraps). The most common example in Python is the key argument to the sorted function.

>>> l = [42, 21, 17, 19, -3]
>>> sorted(l)
[-3, 17, 19, 21, 42]
>>> sorted(l, key=lambda x: x * -1)
[42, 21, 19, 17, -3]
>>>

sorted is a function that accepts a key which is simply another function. Less common, but fairly regular examples in Python are map and filter. Both of these functions accept a function that is applied to the values of an interable.

Currying

Most developers will argue that addition is a function of two arguments that returns a numeric value. e.g. 2 + 2 = 4 Can we look at this a different way? What if we considered the function lambda x: x + 2? It adds two to whatever argument is passed to it. That means that we can think of addition as a function that takes a single argument, and returns a function that adds that argument to another value.

In OCaml, infix operators can be rewritten as binary operators by surrounding them with parenthesis. e.g. 2 + 2 is equivalent to (+) 2 2

utop # let f = (+);;
val f : int -> int -> int = <fun>

The second line should look sort of familiar if you have used Python's type annotations. The difference with ML family languages is that they don't differentiate between arguments and return values because all functions are "curried" by default.

utop # let f = (+) 2;;
val f : int -> int = <fun>

utop # let f = (+) 2 4;;
val f : int = 6
This is not the curry you are looking for

You may be familiar with functools.partial. This function is a curry in spirit, but with the complications that mutable-everything bring. partial is an unfortunate name as we'll see next.

Total and partial functions

I am speaking of mathematical partial functions, not "partially-applied" functions. I have to get into the weeds a little on this one, but it's an important concept. The domain of a function is the set of values in the "input space". The range or co-domain is the set of values in the output space. Here's an example:

def int_to_str(i: int) -> str:
    return str(i)

The domain of this function is all integers and the range or co-domain is the subset of strings that can be translated from integers. This can be a bit of a squishy subject because computers have finite resources. We can say a function works on "all strings", but implicitly, we understand that "all strings" are those we can store and process on a given machine.

Here is another example, Python's math.log:

>>> from math import log
>>> log(-2)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: math domain error
>>>

We have to be careful about how we define the domain of a function. In math class, you have probably heard, "The domain of the natural logarithm is all positive real numbers". In this context, the natural logarithm is a total function. It is defined (an output exists) for every value in the domain.

Programmers tend not to think in those restrictive terms, and thankfully, mathematicians provide us with the terminology to handle these situations. If we expand our definition of domain a bit, then we can consider partial functions. What if I want to define the domain of the natural logarithm as all the reals, positive and negative? In this context, the natural logarithm becomes a partial function because there are elements of the input set that do not map to the output set (range or co-domain). In other words, there are some inputs that are invalid.

The add function defined earlier is total. This is because Python integers are only bound by system resources. The get_val function defined earlier is a partial function. In OCaml, List.hd returns the first element of a list. This function is partial because it will fail on an empty list.

This may sound like a silly mathematical exercise, but looking at your code in this light is an important skill. Partial functions will fail under certain conditions. We can make them total functions through a type system. In a language like Python, we have to rely on data sanitation and validation.

Before you run off and create custom types for all of your functions, consider the tradeoffs. Why doesn't everyone program like this? The reason is because this kind of type safety comes at the cost of complexity. Maybe dealing with an exception is a simpler, more elegant solution to your problem than creating a positive_reals data structure. And maybe the problem in question is a mission-critical piece of business logic, and some of us like to try to sleep soundly at night.

Recursion

Most developers are aware of recursion, and it is supported by most programming languages. Recursion is another first-class feature of functional languages. Haskell has no loops, relying exclusively on recursion. Recursion is inefficient in some languages, and care should be taken when dealing with large data structures. Read about tail recursion in Haskell and OCaml.

>>> l = []
>>> for i in range(10):
...     l.append(i)
...
>>> l
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>>

Don't let the syntax scare you too much. There is a lot to unpack here. This is simply to demonstrate that we don't need loops. One possible recursive solution in OCaml.

utop # let rec f n acc = match n with 
| 0 -> acc
| _ -> f (n - 1) ((n - 1) :: acc);;
val f : int -> int list -> int list = <fun>

utop # let _ = f 10 [];;
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

The rec keyword tells the compiler that this is a recursive function. This defines a function named f that takes an integer n and a list of integers acc. Finally, a list of integers is the return type.

Pattern matching

The switch statement of functional programming, but better and more powerful. This was shown earlier, now I'll break it down a bit.

let rec f n acc = match n with 
| 0 -> acc
| _ -> f (n - 1) ((n - 1) :: acc)

match n with says match this variable with a value (or even a type). The first case is 0 and the underscore means we don't care (OCaml enforces unused variables just like golang). This is useful in a recursive function becaus we can identify edge conditions that signal the termination of the loop. It also saves us from if then Hades. Also notice that there are no types in this function definition! OCaml and Haskell have powerful type inferencing mechanisms, so annotations are rarely needed. Speaking of types, OCaml is strongly-typed, right? Why would we need to be able to match on a type? Read on!

Sum types

Algebraic data types are well-supported in FP languages. An option is a sum type that acts as a container for possibly empty values (see Tony Hoare's talk on the billion-dollar mistake). This is a parameterized type because the inner value takes on the type of the parameter passed to the constructor (I'll explain below).

utop # type 'a option =
| Some of 'a
| None;;
type 'a option = Some of 'a | None

Going back to pattern-matching, we can match on types as well:

let f = function
| Some v -> Some (v + 2)
| None -> None;;
val f : int option -> int option = <fun>

utop # let _ = f v;;
- : int option = Some 44

Notice here that the type isn't 'a option which is our "generic" option. This option has been paramaterized by the int type. OCaml is able to determine this entirely through type-inferencing because we called the + function!

On one hand neat, but on the other hand, am I saying that you have to write special functions just to deal with containers? Don't worry! This isn't golang! The monadic interface is supported as well (monads will get covered in another article). The following code leverages the built-in Option type.

utop # let v = Some 42;;
val v : int Option = Some 42

utop # Option.map ((+) 2) v;; 
- : int Option = Some 44

utop # let v = None;;
val v : 'a option = None
utop # Option.map ((+) 2) v;;
- : int option = None
utop #

These are called sum types because the cardinality of the set is the sum of the cardinalities of the member types of the set. Scott Wlashin has a great video on how this concept is useful to programmers.

Product types

Does that mean there is such a thing as product types? Of course! These are hidden away in what Pythonistas know as tuples.

>>> (42, "abc")
(42, 'abc')
>>> type((42, "abc"))
<class 'tuple'>
>>>

If we were to use a type annotation, it would be Tuple[Int, String]. Looking back at cardinalilities, this is a product type because the cardinality of the combined type is the product of its members. These don't have to be 2-tuples, either, any permutation is allowed.

utop # let t = (42, "forty-two");;
val t : int * string = (42, "forty-two")

Notice the * in the type anotation above. You know, like multiplication! Can we pattern match on product types? Yes!

utop # let f v = match v with
| (42, _) -> "You really like Douglas Adams!"
| _ -> "What a boring tuple";;
val f : int * 'a -> string = <fun>

utop # let _ = f t;;
- : string = "You really like Douglas Adams!"

utop # let _ = f (99, 22);;
- : string = "What a boring tuple"

utop #

You may notice that I didn't provide anything useful in the second argument of the pattern match. This is why the REPL annotates it as 'a. That means that the function will accept any type in that position. The typing system is incredibly powerful once you sort it out in your head.

Next steps

All of these topics are covered in great detail by the smart people of the interwebs. My goal was to introduce these ideas from a Pythonista's frame of mind since Python is still my "daily driver". I didn't cover some important topics like composition and thinking with types. They deserve more thorough coverage, and I hope to tackle each of them in the near future.

Can you use these techniques in Python? Yes, of course! I do encourage you to learn a bit of Haskell or OCaml first. For me, leaving the comfort of Python really made this material "click". You also need to be acutely aware of the limitations of Python and where these constructs fall apart.

My favorite Python/FP libraries