Compose Yourself: Fun with Functions

Scott Sauyet

Javascript is the love-child of Self and Scheme

From Self, a powerful, if somewhat unusual, OO system
- Dynamic dispatch
- Encapsulation
- Polymorphism — lots of it (weak typing!)
- Inheritance through the prototype chain
- Open recursion — through `this`
From Scheme, the most important features of functional languages
- First class functions
- Closures

We're going to ignore the OO stuff altogether and focus on one application of first-class functions.

New Functions From Old!

Functional Composition chains together functions to create a new function.

// Simple compose

var trim = function(str) {return str.replace(/^\s*|\s*$/g, '');};
var capitalize = function(str) {return str.toUpperCase();};

var convert = compose(trim, capitalize);

console.log('"' + convert('   abc def ghi  ') + '"');

Techniques

There are many ways to create compose functions. We'll examine a few of them.

We will glance at the implementations, but mostly focus on the APIs presented by these techniques.

Our Test Functions

We will use these functions for our tests throughout:

// Basic Test Functions

var add1 = function(x) {return x + 1;};
var mult2 = function(x) {return x * 2;};
var square = function(x) {return x * x;};
var negate = function(x) {return -x;};

console.log(add1(42));
console.log(square(7));

Question: What value will this code yield?

var f = compose(add1, square);
console.log(f(7));

Mathematical Composition

In mathematics f ∘ g (pronounced "f composed with g") is the function that given x, returns f(g(x)).

So if we follow the mathematical model compose(add1, square)(x) should equal add1(square(x)).

Simplest Implementation

// Simplest compose

var compose = function(f, g) {
    return function(x) {
        return f(g(x));
    };
};

Several flaws

var compose = function(f, g) {
    return function(x) {
        return f(g(x));
    };
};

This naive implementation has at least two flaws:

It loses track of the this context used to call it.
It ignores all but the first argument passed to the initial function.

But it's simple to fix those:

var compose = function(f, g) {
    return function() {
        return f.call(this, g.apply(this, arguments));
    };
};

Prototype Manipulation

We can make composition a property of all functions by modifying the Function prototype.

Function.prototype.compose = function(g) {
     var fn = this;
     return function() {
         return fn.call(this, g.apply(this, arguments));
     };
};

var f = mult2.compose(square).compose(add1);
console.log(f(5));

This example doesn't work in this presentation sandbox, but will work in browser. It can be demoed in the console.

There are those who will tell you not to alter the native prototypes, and perhaps they have good points, but ...

what I think is funny about JS is that everyone told you not to pollute native prototypes while most of recent standards come from who did!

Multiple functions

It's easy enough to extend this to multiple functions:

var compose = function() {
    var funcs = arguments;
    return function() {
        var args = arguments;
        for (var i = funcs.length; i --> 0;) {
            args = [funcs[i].apply(this, args)];
        }
        return args[0];
    };
};

var f = compose(negate, square, mult2, add1);
console.log(f(2));

This is very similar to Underscore's code.

We could do this with the prototype version as well, although that might feel strange.

Argument Types

Our examples have used functions that returned the same type they accepted. This is not important. The essential feature is that each function accept the same type its predecessor generated:

var after = function(chr) {
    return function(str) {  // String ==> String
        var index = str.indexOf(chr);
        return (index < 0) ? "" : str.substring(index + 1);
    };
};

var splitOn = function(chr) {
    return function(str) {  // String ==> [String]
        return str.split(chr);
    };
};

var makeObj = function(desc) {  // [String] ==> Object
    return desc.reduce(function(obj, str) {
        var parts = str.split("=");
        obj[parts[0]] = parts[1];
        return obj;
    }, {});
};

var url = "http://example.com/fetch?product=widget&color=red&size=6";

var getConfig = compose(makeObj, splitOn("&"), after("?"));

console.log(getConfig(url));

Coding is not Mathematics

Reading these from right-to-left is... odd. There are several options:

Reverse the order (compose(f, g) ~~> g(f(x))
But this won't match many people's expectations of compose.
Add a similar pipe or sequence function to do the reverse of compose.
But this expands the API surface area without adding functionality
Make a compose with a different enough API that no one expects the mathematical behavior.

We'll look at some ways of doing this next.

Variadic composition through multiple invocations

This API makes it more obvious that the functions should be read from left-to-right:

var f = compose(add1)(mult2)(square)(negate)();

console.log(f(2));

Implementation:

var compose = function compose(f) {
    var queue = f ? [f] : [];
    var fn = function fn(g) {
        if (arguments.length) {
            queue.push(g);
            return fn;
        }
        return function() {
            var args = Array.prototype.slice.call(arguments);
            queue.forEach(function(func) {
                args = [func.apply(this, args)];
            });
            return args[0];
        }
    };
    return fn;
};

Explicit ordering

We can make the ordering of functions entirely explict:

var f = first(add1).then(mult2).andThen(square).andFinally(negate);

var g = first(mult2).next(add1).then(negate).then(mult2)
                    .then(add1).last(square);

console.log(f(2));
console.log(g(3));

This API makes a miniature DSL out of functional composition, always starting with "first", followed by any number of "then", "andThen", or "next" clauses, optionally concluding with "finally", "last", or "andFinally".

It is more verbose, but is extremely explicit.

Explicit Ordering Implementation

var first = (function() {
    var chainNames = ["then", "andThen", "next"];
    var endChainNames = ["finally", "andFinally", "last"];
    var chain = function(fn) {
        var f1 = function(g) {
            var func = function() {return g.call(this,
                    fn.apply(this, arguments));};
            chain(func);
            return func;
        };
        var f2 = function(g) {
            return function() {return g.call(this,
                    fn.apply(this, arguments));};
        };
        chainNames.forEach(function(name) {fn[name] = f1;});
        endChainNames.forEach(function(name) {fn[name] = f2;});
    };
    return function(f) {
        var fn = function() {
            return f.apply(this, arguments);
        };
        chain(fn);
        return fn;
    };
}());

Operator Overloading

What if we overloaded the right-shift operator?

var f = Ω()(add1 >> mult2 >> square >> negate);
var g = Ω()(mult2 >> add1 >> negate >> square >> add1);
var h = Ω()(f >> g >> add1);

console.log(f(2)); // 36
console.log(g(3)); // 50
console.log(h(1)); // 963

This doesn't work in this presentation sandbox, but will work in browser. It can be demoed in the console.

Operator overloading in JS? WTF?.

Fake it until you make it!

Fake Operator Overloading Implementation

var Ω = function() {
    var queue = [];
    var valueOf = Function.prototype.valueOf;
    Function.prototype.valueOf = function() {
        queue.push(this);
        return 1;
    };
    return function() {
        Function.prototype.valueOf = valueOf;
        return function(x) {
            for (var i = 0, val = x, len = queue.length; i < len; i++) {
                val = queue[i](val);
            }
            return val;
        }
    };
};

// var f = Ω()(add1 >> mult2 >> square >> negate);

This doesn't work in this presentation sandbox, but will work in browser. It can be demoed in the console.

Not for real-world usage

This is just a fun exercise to show what can be done. Please don't try this at home!

Wrap-up

To mathematicians, functional composition is a simple concept. Translating it into code can lead to some interesting and complex API decisions.

There is clearly no right answer. Except for the operator overloading one, every one of those implementations has a claim to be the one you might choose.

And that's it except for ...

The Obligatory Compose Joke

Questions?

Resources

Javascript Functional Programming Libraries:
- allong.es: http://allong.es/
- Lemonad: http://fogus.github.io/lemonad/
- Functional Javascript: http://osteele.com/sources/javascript/functional/
Other Useful Javascript Libraries
- Underscore: http://underscorejs.org/
- Lo-Dash: http://lodash.com/
Books on Functional Programming
- The Little Schemer, Daniel P. Friedman and Mattias Felleisen
- Structure and Interpretation of Computer Programs, Harold Abelson, and Gerald Sussman with Julie Sussman
- Learn You a Haskell for Great Good, Miran Lipovača,
Performance enhancement technique for composition: http://www.codedodger.com/2013/02/variadic-composition-without-recursion/
This presentation: http://scott.sauyet.com/Javascript/Talk/Compose/
Contact Me: scott.sauyet@gmail.com | https://github.com/CrossEye