Higher order functions

Previously we talked about recursion, a way of programming in which we define a case and a step and let the software produce magic. We also touched on the functional programming paradigm. Today I want to add another topic from the functional programming arena: higher order functions.

Let’s start with an example this time. Suppose we have an array of numbers, say 10 random numbers. How quick can you get me the square root of every number?

function squareRootArray($array)
{
      $returnValue = array();
      foreach ($array as $index => $value(
      {
            $returnValue [$index] = sqrt($value);
      }
      return $returnValue;
}

What about the natural logarithm of every number?

function logArray($array)
{
      $returnValue = array();
      foreach ($array as $index => $value(
      {
            $ returnValue [$index] = log($value); // Only different line!
      }
      return $ returnValue;
}

Not too bad. Now how quickly can you give me the product of all the numbers?

function productArray($array)
{
      foreach ($array as $value)
      {
            if (!isset($returnValue)
            {
                  $returnValue = $value;
            }
            else
            {
                  $returnValue *= $value;
            }
      }
      return $returnValue;
}

Or the sum of all the numbers?

function sumArray($array)
{
      foreach ($array as $value)
      {
            if (!isset($returnValue)
            {
                  $returnValue = $value;
            }
            else
            {
                  $returnValue += $value; // Only different line!
            }
      }
      return $returnValue;
}

Do you see the patterns? In both pairs of examples there is only one line, even one function application that differs. The difference between the pairs is that one pair is about applying a function to every element of an array and the other is about producing a scalar value for an entire array.

Functions as arguments

A higher order function is a function that takes another function as an argument. For example, in PHP we can define a function ‘applyfunction’ with three arguments a, b and function as follows:

function multiply($a, $b)
{
      return $a * $b;
}

function applyFunction($a, $b, $function)
{
      return $function($a, $b);
}

echo applyFunction(5, 6, “multiply”); // should put 30 on the screen

Here applyFunction is a somewhat useless, but higher order function nonetheless.

Map and reduce

The first two pairs of examples were about two well-known higher order functions: map and reduce. A typical map function takes an array and a function that takes one argument and executes the function for every value in the array. Similarly, a typical reduce function takes an array and a function that takes two arguments and calls the function on every value in the array and the intermediate result. Here are two example PHP implementations: (Don’t bother using them, PHP has better)

function map($array, $function)
{
      $returnValue = array();
      foreach ($array as $index => $value(
      {
            $ returnValue [$index] = $function ($value);
      }
      return $ returnValue;
}

function reduce($array, $function)
{
      foreach ($array as $value)
      {
            if (!isset($returnValue)
            {
                  $returnValue = $value;
            }
            else
            {
                  $returnValue = $function($value, $returnValue);
            }
      }
      return $returnValue;
}

For clarity’s sake: there are actually two common reduce functions. That’s because there is a (sometimes implicit) ordering in every array and that means you can approach the array in two ways: left to right and right to left. That’s why you will usually find fold instead of reduce irl, foldl and foldr.

Anonymous functions

Because it would be such a bother to have to name every function you want to use as an argument for a higher order function, people invented anonymous functions. When declared, these functions are not named, but instead returned as a variable, so that they may be executed later. The following examples rewrite the first four examples with anonymous functions passed to map and reduce:

// would be silly to use anonymous functions here
$squareRoots = map(range(1, 10), “sqrt”);
$naturalLogs = map(range(1,10), “log”);

// anonymous functions!
$product = reduce(range(1,10),
      function($value, $returnValue) { return $value * $returnValue; });
$sum = reduce(range(1,10),
      function($value, $returnValue) { return $value + $returnValue; });

Mind that there is a difference between anonymous functions and closures. In the PHP community the two are often used as synonyms, but there is a small difference.

A closure can still use variables from the scope it was created in, but this is not necessarily the case for an anonymous function. So any closure is an anonymous function, but not all anonymous functions are closures. JavaScript uses full-on closures, where PHP really uses anonymous functions that can have variables injected into their scope with the use keyword.

MapReduce

Now, these techniques are not just fair tricks. Oh no sir, understanding what happens with map and reduce brings great competitive advantages. Besides being generally more elegant on the eyes, saving LOCs and making more code re-use possible, one huge advantage I want to share with you is that the ability to map and reduce is the ability to split a large problem into a bucket load of smaller problems. The fantastic thing about higher order programming is that you separate the how of the problem from the problem domain itself. The programming solution is on a different architectural level than the computing solution. This means that you can have the seriously smart people working on the less difficult programming solution, so that you can have the astronomically smart people working on how to make computers understand the code with nifty tricks like function currying, lambda calculus, graph rewriting and all those other buzzwords I learned in school but always have a hard time following.

This is exactly what Google did. Google has built their patented software framework MapReduce to have a master machine map out the problem to all sorts of worker machines and get the answers back to reduce the answers to a single answer to the problem. This platform has given Google a significant competitive advantage over its, euh, competitors.

Concluding

Ok, fun, but what use is this? What can YOU, dear reader, take from this article?

Well, I want you to take away from this (really, from all my articles) that learning and keeping an open perspective is essential. It can provide you with just that edge case that your colleagues or competitors don’t know about and thus make you that much more valuable an asset. And it’s fun to brag about stuff you know, of course!

So realize that some languages are fun to explore, but don’t give you the entire spectrum of what programming is. Programming is more than OOP, programming is more than stepwise telling the computer to lift its left leg! now its right leg!

Keep looking, keep learning.

Ps. For funzies.

At university I have programmed in a lot of different languages and paradigms, some of which may even scarcely be called programming. Here is a list of some interesting languages I have come across and dabbled with:

• Logical: Prolog & Otter, CDL3
  (interesting, but don’t, reall. Just don’t)
• Functional: Clean & Haskell
  (tip, really check this out! Here’s a decent tutorial.)
• OOP: Java
• Imperative (mostly): C, C++
  (also really check this out, try and implement data structures and sorting algorithms)
• Wtf, euh, very imperative: UltraSparc assembler, X86 assembler