Dictionaries are Pure Functions (Part 1)

Putting the Function in Functional Programming

A lot of languages are adding features inspired by functional programming these days. Even if you don’t consider yourself a functional programmer, you’ve probably had an opportunity to use features like pattern matching, anonymous functions, closures, or higher order functions like map and filter. After getting some experience using these features and seeing how they can help you write simpler more reliable code, you might be interested in taking a deeper look at pure functional programming.

When you first start looking into pure functional programming, it can look a bit intimidating. One of the biggest challenges is that terms you’re familiar with are often used in slightly different ways, and concepts you’re used to using are applied in fundamentally different ways. It’s not that pure functional programming is harder per se, but it’s different, and it’s sometimes easy to get some way down the path of learning about functional programming only to find that there were some fundamentals you may have missed along the way that are making it harder than expected to keep moving forward.

Functions, pure functions in particular, are one of the most common examples of something that can be a surprising barrier to learning about functional programming. Given the name, it’s no surprise that functions are an important part of functional programming. Even though someone coming to functional programming from an object oriented or procedural background will already be familiar with functions, functional programmers tend to think about functions just a little bit differently, and that difference sometimes turns into a barrier.

In this post we’ll try to help you avoid this problem by helping you learn how to think about pure functions the way a functional programmer does. We’ll start working in python, and gradually build up an intuition for how to think about typed pure functions incrementally. Toward the end of the article we’ll also look at a couple of examples in Haskell to illustrate how what we learned from the python examples can be extended to help us understand fairly advanced techniques in pure functional code.

What are functions, anyway?

When we’re working in procedural code, we generally think of functions as a way to do something in a reusable way. For example, we might write a function that asks a user for their name and then prints a greeting to the screen:

def greet():
    name = input("What's your name? ")
    print(f"Hello, {name}")

Sometimes, we pass some arguments into a function to allow us to configure what it does, like this function that lets us pass in a message to configure the greeting that we show to the user:

def greetWithMessage(message):
    name = input("What's your name? ")
    print(f"{message}, {name}")

It’s also pretty common for our functions to give us back a value, like this function that gives us back a user’s full name:

def getFullName():
    firstName = input("What's your first name? ")
    lastName = input("What's your last name? ")
    return firstName + " " + lastName

In object oriented code, we often think about methods rather than functions. Like procedural functions, we often think of an object’s methods in terms of what it does. Methods are part of an object, so we usually think about their behavior in terms of what they do to a particular instance of our object. For example, in a Stack class we might have a number of methods that do the work of adding or removing items from our stack:

class Stack:
    def __init__(self):
        self.head = None

    def push(self, val):
        rest = self.head
        self.head = (val, rest)

    def pop(self):
        if self.head == None:
            return None
        (head, rest) = self.head
        self.head = rest
        return head

This idea that a function does something is fundamental to the way we think about them in procedural and object oriented code, even we’re writing functions that only work with their arguments and return a value. As an example, read the function below and think about how you might explain it to someone:

def addNumbersInList(listOfNumbers):
    total = 0
    for number in listOfNumbers:
        total = total + number
    return total

Although you might have come up with a different description, here’s a common way we might explain this function:

This explanation of the function is characteristic of the way that we focus on the act of computation in procedural and object oriented code. While it’s a perfectly good explanation of the behavior of our function, it’s also quite different from the way a functional programmer might describe it. In functional programming, it’s more common to think about functions as expressions that relate values. Although functions in a functional program might still need to do some work to arrive at a value, the computations that are carried out aren’t the focus.

Whether we choose to view functions through the lens of the computations they carry out or through the lens of the way they relate values has an impact on the way we think about using them in our code. Taking a computational view of functions may make it easier to reason about some programs, but it can make it harder to fully understand some common patterns in functional code like recursion and higher order functions.

Later, we’ll spend some time trying to develop an intuition for how to think of functions as a relationship between values using something that will probably be quite familiar to you: dictionaries.

Dictionaries are Pure Functions

When you are first learning about functional programming you’ll hear people talk a lot about pure functions. Most material assumes that you know what a pure function is. If you delve deeper and start trying to understand what functional programmers mean when they talk about pure functions, you’ll probably get one of two common explanations:

• Pure functions are functions that don’t have side effects
• Pure functions are like mathematical functions that take a single argument and return a value

Unfortunately, neither of these explanations are particularly helpful when you’re trying to get your head around how to think about functional programming. The idea of programming without side effects seems overwhelming, and perhaps even useless, because we’re used to thinking about functions as code that does something. When we’re told that pure functions are functions that by definition can’t do things it’s hard to imagine how to build anything useful. Trying to think about pure functions as mathematical functions may be even worse, because our minds immediately jump back to all of the math courses we’ve taken and the functions we dealt with that were very unlike the kind of things that we typically write programs to do.

Instead of getting hung up on these definitions, there’s a different way that we can look at pure functions that can help us understand them more clearly:

Thinking of functions this way might remind you of another common way that we relate one value to another: dictionaries. This turns out to be a very good analogy, and it can be an effective way to learn how to start thinking about functions through the lens of functional programming. Let’s spend some time looking at how we can put this idea into practice by implementing some code using both functions and dictionaries. We’ll start by looking at some basic examples of functions that take arguments and return a value. Next, we’ll look at how thinking of functions as dictionaries can make it easier for us to write higher order functions- that is, functions that take other functions as arguments, or return new functions. Finally, we’ll look at how thinking of functions as dictionaries can make it easier for us to visualize how recursive functions work. Along the way we’ll also take a look at how dictionaries can help us think about the types of our functions.

Implementing Simple Functions as Dictionaries

When we start thinking about the equivalence between dictionaries and functions, the most straightforward examples are functions where we can easily list out all of the values we might pass in and what the function returns. As an example, let’s look at a function that inverts a boolean value:

def invert(a: bool) -> bool:
    return not a

This function isn’t particularly interesting on it’s own since it’s just calling Python’s built-in not operator, but it does give us a good starting place to think about how to create a equivalent dictionary since it’s easy to manually list out all of the values we could pass into the function, and what values the function will return.

Since our function takes a single boolean value, there are only two cases we need to consider. We’ll either pass in True or False. The inverse of True is False, and the inverse of False is True. We can easily hardcode this behavior into a dictionary:

invertDict: Dict[bool, bool] = {True: False, False: True}

Whether we call a function or look up a value in our dictionary, the result will be the same:

>>> invert(True)
False
>>> invert(False)
True
>>> invertDict[True]
False
>>> invertDict[False]
True

In this example you can see that our dictionary and our function are equivalent, although exhaustively writing out the dictionary was more verbose. In some cases though, the equivalence works in the other direction. For example, imagine that we want to write a function that will let us turn clockwise on a map, going from north to east to south to west. Let’s take a look at how we might approach this using both a function and a dictionary:

class CardinalDirection(Enum):
    North = "North"
    East = "East"
    South = "South"
    West = "West"

def clockwise(direction: CardinalDirection) -> CardinalDirection:
    match direction:
        case CardinalDirection.North:
            return CardinalDirection.East
        case CardinalDirection.East:
            return CardinalDirection.South
        case CardinalDirection.South:
            return CardinalDirection.West
        case CardinalDirection.West:
            return CardinalDirection.North

clockwiseDict: Dict[CardinalDirection, CardinalDirection] = {
    CardinalDirection.North: CardinalDirection.East,
    CardinalDirection.East: CardinalDirection.South,
    CardinalDirection.South: CardinalDirection.West,
    CardinalDirection.West: CardinalDirection.North
}

In this example you can see that it’s our function that’s more verbose than our dictionary. In our dictionary we can simply provide the output value that’s associated with each input. Our function has to go a step further and first pattern match on the input before returning a result. Once again, of course, no matter which way we choose to write our code the results we get back are the same:

>>> clockwise(CardinalDirection.North)
<CardinalDirection.East: 'East'>
>>> clockwise(CardinalDirection.East)
<CardinalDirection.South: 'South'>
>>> clockwise(CardinalDirection.South)
<CardinalDirection.West: 'West'>
>>> clockwise(CardinalDirection.West)
<CardinalDirection.North: 'North'>

>>> clockwiseDict[CardinalDirection.North]
<CardinalDirection.East: 'East'>
>>> clockwiseDict[CardinalDirection.East]
<CardinalDirection.South: 'South'>
>>> clockwiseDict[CardinalDirection.South]
<CardinalDirection.West: 'West'>
>>> clockwiseDict[CardinalDirection.West]
<CardinalDirection.North: 'North'>

We’ve just looked at two examples that compare functions to hard-coded dictionaries. One one case our function was a bit simpler and shorter to write, in the other the dictionary had the advantage. In both cases, we were able to rely on the fact that there were only a few possible values that we needed to consider. What about functions that might take a much larger number of values? As an example, let’s imagine a function that increments a number:

def increment(x: int) -> int:
    return x + 1

This function can take in any integer value and will return the next largest integer value. In Python, integer values are unbounded, meaning that an integer value can be as large as we’d like and isn’t restricted to a particular number of bytes. Since it would be impossible for us to write out an infinitely large dictionary, let’s pretend for the moment that we’re working with unsigned 8-bit integers that will have a value between 0 and 255. Later in this section we’ll look at ways we could deal with larger (but finite) numbers, and toward the end of this article we’ll touch on some techniques you could use to create dictionaries that need an infinite number of keys.

For now, let’s try using the same technique we used for invertDict and clockwiseDict to create a dictionary version of increment:

incrementDict: Dict[int, int] = {
    0: 1,
    1: 2,
    2: 3,
#   ... many lines omitted
    254: 255,
    255: 256
}

If you were to type this example out, including all of the lines that were omitted for the sake of brevity, it would work. It’s also plainly a terrible way to build software, and one that couldn’t possibly scale up in any reasonable way. Thankfully we have better options. We can use Python’s dictionary comprehensions to define our dictionary much more easily. Let’s try to implement incrementDict this way instead of hard-coding each value:

incrementDict: Dict[int, int] = {x: x + 1 for x in range(255)}

Using our dictionary comprehension we’re still creating a mapping from keys to values, but now we’re doing so by providing a computation that we can use to transform each key into the value it’s associated with.

As before, you can load up both the function and dictionary definitions of increment into your REPL to play with, and you can see that they behave the same way:

>>> increment(5)
6
>>> incrementDict[5]
6
>>> increment(223)
224
>>> incrementDict[223]
224

Functions With Multiple Arguments

By now you should see how functions like invert and increment that take a single argument and return a value are analogous to dictionaries, but a lot of the functions we use in the real world take many arguments. Since we’ve been talking about how pure functions relate a single input to some result, it might seem unintuitive that we can still easily create dictionaries for functions that take multiple arguments. To better understand how this works, let’s start by looking at a function that re-implements the and operator and returns True if both of its arguments are True:

def both(a: bool, b: bool) -> bool:
    return a and b

There are a couple of different ways that we can think about functions that take multiple arguments. In procedural and object oriented languages, we tend to think about functions that take multiple arguments as though they take all of their arguments at once as a single value. In this example, we can create a dictionary whose keys are tuples of two boolean values. This will let us treat each unique combination of arguments as a value we can associate a result with:

bothDict: Dict[tuple(bool, bool), bool] = {
    (True, True): True,
    (True, False): False,
    (False, True): False,
    (False, False): False
}

or, using dictionary comprehension syntax:

bothDict: Dict[tuple[bool, bool], bool] = {
    (x, y): x and y for x in [True, False] for y in [True, False]
}

Functional programmers often refer to this style of function, where we handle all of the arguments together, as an uncurried function. In functional programming, it’s more common instead to think about curried functions. Like all of the functions we’ve looked at so far, a curried function takes a single input and associates it with a particular return value. Instead of combining all of our arguments into one value, in a curried function we take arguments one at a time, each time returning a new function that takes the next value. Let’s look at how we’d implement this using functions first, then look at the dictionary equivalent.

def bothCurried(a: bool) -> Callable[[bool], bool]:
    def f(b):
        return a and b
    return f

We can shorten this code a bit by using the lambda keyword to create an anonymous function that we return directly:

def bothCurried(a: bool) -> Callable[[bool], bool]:
    return lambda b: a and b

Calling curried functions requires that we first call the outer function with an initial value, and then call the function it returns with our second value. Let’s look at an example:

>>> bothCurried(True)(True)
True

>>> bothCurried(True)(False)
False

>>> bothCurried(False)(False)
False

One advantage that we get with curried functions is that we can easily apply one argument and leave other arguments to be applied later. We often refer to these as partially applied functions. You’ll see later on how this can be useful when using higher order functions. For now, we can look at a simple example:

>>> partialTrue = bothCurried(True)

>>> partialTrue(False)
False

>>> partialTrue(True)
True

It’s common for people to struggle to wrap their heads around curried and partially applied functions when they are first introduced to them. This is a good example of how thinking about functions in terms of dictionaries can help us get a better understanding of the functional programming view of functions.

Before we look at how to translate this function into a dictionary, let’s go on a short side quest to look at how we’d parse a json document in python and then access some fields. Imagine that we have a json document with information about planets in the solar system:

{
  "sol_system": {
    "mercury": {
      "type": "rocky",
      "day_length": 59,
      "moons": 0
    },
    "venus": {
      "type": "rocky",
      "day_length": 243,
      "moons": 0
    },
    "earth": {
      "type": "rocky",
      "day_length": 1,
      "moons": 1,
      "atmosphere": ["nitrogen", "oxygen"]
    },
    "mars": {
      "type": "rocky",
      "day_length": 1.03,
      "moons": 2,
      "atmosphere": ["carbon dioxide", "argon", "nitrogen"]
    },
    "jupiter": {
      "type": "gas giant",
      "day_length": 0.41,
      "moons": 79,
      "atmosphere": ["hydrogen", "helium"]
    },
    "saturn": {
      "type": "gas giant",
      "day_length": 0.45,
      "moons": 83,
      "atmosphere": ["hydrogen", "helium"]
    },
    "uranus": {
      "type": "ice giant",
      "day_length": 0.72,
      "moons": 27,
      "atmosphere": ["hydrogen", "helium", "methane"]
    },
    "neptune": {
      "type": "ice giant",
      "day_length": 0.67,
      "moons": 14,
      "atmosphere": ["hydrogen", "helium", "methane"]
    }
  }
}

If we load this json document into a python value, we’ll get a set of nested dictionaries that we can use to access the data. For example:

>>> __import__('json').load(open("planets.json"))

>>> planets["sol_system"]["earth"]["day_length"]
1

>>> planets["sol_system"]["neptune"]["atmosphere"]
['hydrogen', 'helium', 'methane']

Nested dictionaries are something we work with regularly when dealing with hierarchical data. We can use this same idea to create dictionaries that mirror curried functions. For example, if we want to hard-code a nested dictionary version of bothCurried we might say:

bothDictCurried: Dict[bool, Dict[bool, bool]] = {
    True: {True: True, False: False},
    False: {True: False, False: False}
}

Alternatively, using a dictionary comprehension:

bothDictCurried: Dict[bool, Dict[bool, bool]] = {
    x: {y: x and y for y in [True, False]} for x in [True, False]
}

For functions that deal with inputs types that have more values, we can apply the same techniques. For example, let’s write a curried function that adds two numbers together, and also create an equivalent dictionary:

def addCurried(a: int) -> Callable[[int], int]:
    return (lambda b: a + b)

addDictCurried: Dict[int, Dict[int, int]] = {
    x: {y: x + y for y in range(255)} for x in range(255)
}

Let’s try running these in our REPL:

>>> addCurried(1)(2)
3
>>> addDictCurried[1][2]
3

>>> addTwo = addCurried(2)
>>> addTwo(1)
3
>>> addTwo(2)
4

>>> addTwoDict = addDictCurried[2]
>>> addTwoDict[1]
3
>>> addTwoDict[2]
4

As you work through these examples you may notice that the dictionary based version of our function feels more natural, both when you are calling it with two arguments and when you are partially applying it. Even though the syntax for using our curried addition function is very similar to the dictionary. When you are used to thinking of functions as computations it can feel unnatural to work with them the way we work with data. Focusing on the ways that functions are a mapping from an input value to a result can help this style of programming feel more natural.

Stay Tuned for Part 2

That’s it for now. Stay tuned for part 2 where we’ll cover:

• How closures are like partial application
• Higher order functions as dictionaries
• Recursive Functions as Dictionaries
• Looking Up A Value Doesn’t Have Side Effects
• Keys and Values are Types