2.6. Procedural Abstraction: Map, Curry, and Compose¶

2.6.1. The Mapping Pattern¶

Abstraction is one of the most powerful tools in programming. But what is it? Let’s begin getting our head around this notion by considering the following two examples called addBonusPoint and doubleAll.

1 / 5 Settings

<<<>>>

Both addBonusPoint and doubleAll use very similar patterns of computation. Given a list ns, they return a new list by applying a function (i.e., add1 for addBonusPoint and doubleIt for doubleAll) to every element of the given list. This is done by calling the function with the head of the list and then consing that result onto what recursion returns from the tail of the list. This pattern is highlighted in red below.

var add1 = function (x) {
return fp.add(x,1); };
var addBonusPoint = function (ns) {
if (fp.isNull(ns))
return [ ];
else
return fp.cons(
add1(fp.hd(ns)),
addBonusPoint(fp.tl(ns)));
}
addBonusPoint( [3, 2, 5, 8] );

var doubleIt = function (x) {
return fp.add(x,x); };
var doubleAll = function (ns) {
if (fp.isNull(ns))
return [ ];
else
return fp.cons(
doubleIt(fp.hd(ns)),
doubleAll(fp.tl(ns)));
}
doubleAll( [3, 2, 5, 8] );

Saving...

Server Error
Resubmit

This pattern of computation in the preceding example is called the mapping pattern: it takes a function and a list and returns the list obtained by applying the function to each element in the input list. The following problem is about the mapping pattern.

2.6.2. Function Composition¶

The next example of abstraction we will consider is called function composition. We want a function called compose that takes in two functions f and g and returns the function that first applies g to its argument and then applies f to that result. In other words:

$compose(f,g)(x) = (f \circ g)(x) = f( g(x) )$

Note that the function $f \circ g$ is sometimes called “f after g” or “f following g” because, when the two functions are composed in this order, g is applied first and f second. In contrast, in the composed function $g \circ f$ , read “g after f”, f would be applied first and g second.

1 / 6 Settings

<<<>>>

When we "translate" the definition of compose above into JavaScript, first note that compose is a function that takes in two functions (i.e., f and g) and then uses those to build a new function.

var compose = function (f,g) {
return function (x) {
return ???????;
return f( g(x) );
};
};
var h = compose( function (x) { return x*x; },
function (x) { return x+1; });
h(4);

Saving...

Server Error
Resubmit

The following problem is about function composition.

2.6.3. Currying¶

In the map function we developed earlier:

  var map = function (f,ns) {
  if (fp.isNull(ns))
      return [ ];
  else
      return fp.cons(
                      f(fp.hd(ns)),
                      map(f, fp.tl(ns))
                    );
};

we cannot separate the computations we want to do on list elements, for example, “doubling all of the elements of a list” or “incrementing all of the elements of a list” from their argument list because the map function needs both of its arguments simultaneously.

Instead, we would like to write a function, map1 below, that takes in only a function, for example doubleIt, and returns another function, in our example, the function doubleAll that can be applied in general to all lists of numbers. map1 is a function-creating function whereas map is not.

var map1 = function (f) {
  return function (ns) {
     if (fp.isNull(ns))
       return [ ];
     else
       return fp.cons(f(fp.hd(ns)), map1(f)(fp.tl(ns)));
    };
};
var doubleAll = map1(doubleIt);
doubleAll( [1,2,3,4,5] );

Currying is the process of transforming a function that takes two or more arguments (such as map) into a function (such as map1) that takes the first argument and returns another function that takes in the second argument and returns another function that has the first argument “wired into it” because of the closure that is created by the definition of the outer function. This process is named after renowned logician Haskell Curry.

So our map1 function is a curried version of our map function.

We will abstract this currying pattern by writing a function called curry that curries any two-argument function:

var curry = function (f) {
   return function (x) {
      return function (y) {
         return f(x,y);
      };
   };
};

Now we no longer need to write map1 but instead can have curry create it for us.

var map1 = curry(map);

As another example of using curry, consider the following fillIn function:

1 / 7 Settings

<<<>>>

Consider the following function fillIn, which takes two integer arguments.

var fillIn = function(n1,n2) {
if (fp.isEq(n1,n2))
return [n1];
else if (fp.isLT(n1,n2))
return fp.cons(n1, fillIn( fp.add(n1,1), n2));
else
return fp.cons(n1, fillIn( fp.sub(n1,1), n2));
};
var countFrom = curry(fillIn);
var countFrom3To = countFrom(3):
countFrom3To( 6 );
curry(fillIn)(3)(6); // countFrom3To anonymously

Saving...

Server Error
Resubmit

Although the above example may seem a bit contrived, the importance of currying cannot be overstated. It allows us to convert any function of two arguments into a function of one argument that returns a function of one argument. We will return to the importance of doing this in Chapter 3 when we discuss the lambda calculus.

The next problem is about both currying and function composition.

2.6.4. More currying¶

The final problem in this section on procedural abstraction will give you intensive practice with the curry and compose functions. This problem is randomized and must be solved three times in a row.

Programming Languages

Chapter 2 Functional Programming

2.6. Procedural Abstraction: Map, Curry, and Compose¶

2.6.1. The Mapping Pattern¶

2.6.2. Function Composition¶

2.6.3. Currying¶

2.6.4. More currying¶