May 26, 2019

Lifting for huge gains

People tend to be given models about how a particular concept works in a particular programming language, and use that understanding as the basis for how to understand the concept in general. This makes sense in the context of a particular framework or idea which has been ported to different languages. Once you have learned something in one language, it is easy to transfer the knowledge to another language. This process reinforces a particular mental model of how things work, and makes alternative interpretations harder to comprehend. I believe this is one of the reasons learning functional programming is difficult for experienced programmers, and I want to share some insight which has been opening my mind recently.

First, to give a motivating example.

Say we are running a business which upgrades numbers, and have invented the following function:

def upgrade(number):
   return number * 100

This automatically makes any number one hundred times better!

Say we’ve been running this function manually each time someone requests a number, but now there is too much demand for us to keep up. So we decide we need a new function to upgrade a batch of numbers.

The thought process might go something like this:

  • For each number in the batch:
    • Upgrade the number,
    • Put the upgraded number into a result array.
  • Return the result array.

This translates directly to Python:

def batchUpgrade(numbers):
   result = []
   for n in numbers:
      result += upgrade(n)
   return result

Maybe you’re smart and realise this loop is already encapsulated by Python’s built-in map function, and write a one-liner instead:

def batchUpgrade(numbers):
   return map(upgrade, numbers)

Now say a year has passed, and we’re getting overloaded again. Not only do our customers want us to upgrade lots of numbers at a time, but we also have lots of customers! So we want to process the batches… in batches.

For the purposes of this example, let’s say that another thing has happened:

def batchUpgrade(numbers):
   # Developer note: Removing this line kills the job dispatcher; TODO find out why
   emailCustomer(DependencyInjection.currentCustomer, "Please wait while we upgrade your numbers...")
   result = []
   for n in numbers:
      result += upgrade(n)
   emailCustomer(DependencyInjection.currentCustomer, "Your upgraded numbers are " + result)
   return result

Can you see it?

That’s right, we’ve accumulated Technical Debt! Now, we want to upgrade a set of numbers for each customer, all at the same time, and we definitely don’t want it to email anyone while it’s doing that. batchUpgrade has become part of the structural sticky tape holding our system together, so we can’t change it. We’ll have to start over from scratch!

What’s the thought process for changing our new specification into a program?

  • We’ll be getting an array of arrays, representing a set of numbers to upgrade for each customer.
  • A nested array definitely calls for a nested loop.
  • For each of the customer arrays (representing a customer):
    • For each number in that customer’s array:
      • Upgrade the number
      • Put the upgraded number into a customer result array.
    • Put the customer result array into a batch result array.
  • Return the batch result array.

Phew. Luckily this is still pretty simple and translates directly to Python again.

def upgradeWebscale(customerNumberLists):
   result = []
   for customerNumbers in customerNumberLists:
      upgradedCustomerNumbers = []
      for n in customerNumbers:
         upgradedCustomerNumbers += upgrade(n)
      result += upgradedCustomerNumbers
   return result

This is some fairly idiomatic imperative code, but Python once again lets us shorten the code via map:

def upgradeWebscale(customerNumberLists):
   return map(lambda customerNumbers: map(upgrade, customerNumbers), customerNumberLists)

In both of these scenarios, we:

  1. Thought about what input the function should take.
  2. Thought about what output the function should produce.
  3. Thought about what to do with the input to get the output.
  4. Recognised that map already did what we needed to do, and called it.

This is a perfectly reasonable way to design programs, but I will now make the claim that if we had a slightly different understanding of map then we could have avoided most of the thinking involved.

Here is what the Python API documentation says about map:

map(function, iterable, ...)

Return an iterator that applies function to every item of iterable, yielding the results. …

What we learn is:

  • Map takes two arguments: a function, and a collection of things.
  • Map does something to each thing in the collection, in the order they appear.
  • Map produces a collection of results derived from the input collection.

We get the understanding that map gives us a way of iterating over a collection for certain specific use cases.

While this is technically correct and useful, it also puts us in a local maximum of understanding, and this feeling of understanding can prevent us from learning deeper, so we are likely to entirely miss out on a far more general and profound way of understanding map. Let’s have a look!

Here is the Python “signature” of map:

map(function, array)

Which can be called this way:

>>> map(lambda x: x + 1, [1,2,3])

I’m going to use Haskell syntax from now on because it allows me to write type signatures. This is the Haskell equivalent to the Python “signature” and calling example:

map' :: (a -> b, [a]) -> [b]

>>> map' (\x -> x + 1, [1,2,3])

I am intentionally calling it map' (with a quote) for a reason you will discover shortly.

Let’s break this apart. Haskell functions, like mathematical functions, go from exactly one input type to exactly one output type. A function of multiple parameters, like map', is just a function taking a tuple type as input. So map', like the Python map, takes a 2-tuple of function and list, and returns a list.

A spicy interlude.

I want to talk about a process called currying.

If you have a function which takes two arguments - which means you have a function which takes a single 2-tuple argument - then you can always transform it into a function that takes the first element of the 2-tuple and returns a new function. Observe this ASCII art:

f' :: (a, b) -> c
    |        ^
  CURRY      |
    |     UNCURRY  
    V        |
f :: a -> (b -> c)

See how f and f' can each be implemented in terms of the other:

f' :: (a, b) -> c
f' = \(a, b) -> f a b

f :: a -> (b -> c)
f = \a -> (\b -> f' (a, b))

Let’s do a simple example. Say we have a function add' which adds two integers. The ASCII arrows show where the different inputs end up:

add' :: (Int, Int) -> Int
         ---  ---
         /     \
        |       |
        V       v
add :: Int -> (Int -> Int)
add = \x -> (\y -> add' (x, y))

Watch the evaluation process to see how calling add just gives you add':

add 2 3

Expand add to its definition:

(\x -> (\y -> add' (x, y))) 2 3

Apply the outer lambda, substituting 2 everywhere it says x:

(\y -> add' (2, y)) 3

Apply the lambda, substituting 3 everywhere it says y:

add' (2, 3)

And we are left with the original 2-tuple version of add.

Let’s apply the same process to map' (remember, this represents the Python map function). Follow the ASCII arrows:

map' :: (a -> b, [a]) -> [b]
         ------  ---
           |      \
           |       \
           |        \
           v         v
map :: (a -> b) -> ([a] -> [b])
map = \f -> (\as -> map' (f, as))

The following two code snippets are the same:

>>> map' (length, ["hey", "there"])
[3, 5]
>>> map length ["hey", "there"]
[3, 5]

Now we know that this new curried map is equivalent to the original Python map - it’s just been rearranged. But let’s have a closer look at the type signature of curried map:

map :: (a -> b)   ->   ([a] -> [b])

map takes a function and returns a new function. This is totally different to how we understood the Python map, but it’s the same function! Let’s look at exactly how our understanding is collapsing here:

  • It doesn’t seem to take two arguments any more, only one.
  • It doesn’t seem to do anything to a collection.
  • It definitely doesn’t produce a collection of results, because it produces a function.

What does this all mean? Let’s have another look:

map :: (a -> b)   ->   ([a] -> [b])
  • It takes one argument, a function.
  • It lifts the function into a list context.

map takes a function and converts it into a similar function that works on lists. It “listifies” a function. Isn’t that exciting?

Let’s see how this different understanding manifests in our programming thought process.

Say our business is now using Haskell to reduce developer agony. We’ve ported our upgrade function like this:

upgrade :: Int -> Int
upgrade = \x   -> x * 100

We need to write a batch version to keep up with demand. Firstly we write a spec using type signatures:

upgrade :: Int -> Int

batchUpgrade :: [Int] -> [Int]

What’s the thought process for implementing batchUpgrade?

  • The type signature for batchUpgrade looks suspiciously like upgrade.
  • Let’s just lift upgrade into a list context using map.

    batchUpgrade = map upgrade

That’s it, we’re done! What’s that? Our boss wants us to process batches of batches, and not touch or use the existing upgrade function? Let’s write a type signature:

upgrade :: Int -> Int

upgradeWebscale :: [[Int]] -> [[Int]]

upgradeWebscale looks complicated, but let’s follow the thought process now:

  • The type signature for upgradeWebscale looks suspiciously like upgrade.
  • Let’s just lift upgrade twice.

    upgradeWebscale = map (map upgrade)

Done again. Notice how our generalised understanding of map as a lifting operator allowed us to avoid a bunch of annoying thinking. Once this pattern is in your mental toolbox, you will start to see uses for it everywhere.

Powered by Hugo & Kiss.