Functional Programming

Scott Sauyet

An Overview of Functional Techniques
(for non FP'ers) using Javascript

Agenda

What is Functional Programming?
How Functional Programming Differs From Other Paradigms
Functional Programming in Javascript
Advantages and Disadvantages of Functional Style
~~Interaction of Functional and Object-Oriented Styles~~

What is Functional Programming?

No Single Definition

There is no clear, widely-accepted definition of Functional Programming. It is a collection of related featues which cohere well into a very useful style of programming.

Some of these features are readily available in Javascript.
Others can be used if care is taken.
And some are essentially impossible at the language level.

But one of the main points of functional programming is that you can think of results you want, not of the steps you need to take to get them.

Chief difference between OOP and FP

Reg Braithwaite has a good description of the central difference between these two paradigms. OO focuses on the differences in the data, while FP concentrates on consistent data structures.

Object-Oriented

Data and the operations upon it are tightly coupled
Objects hide their implementation of operations from other objects via their interfaces
The central model for abstraction is the data itself
The central activity is composing new objects and extending existing objects by adding new methods to them

Functional

Data is only loosely coupled to functions
Functions hide their implementation, and the language’s abstractions speak to functions and the way they are combined or expressed
The central model for abstraction is the function, not the data structure.
The central activity is writing new functions

What does this mean in the business environment?

Is one of these techniques the clear-cut winner in the business world? Is it functional or object-oriented?

Are you sure?

How much business logic is written like this?

SQL is very similar to functional languages, and it permeates business. It uses a consistent data structure (tables with records organized into columns) and a few basic functions that can be combined into arbitrary queries. And it shares one other important feature with functional languages: it is declarative.

Declarative vs Imperative Programming

One main distinguishing characteristics of functional programming languages is that they describe what they want done, and not how to do it. OO, inside its methods, still uses mostly imperative techniques.

Imperative style

var sumOfSquares = function(list) {
    var result = 0;
    for (var i = 0; i < list.length; i++) {
        result += square(list[i]);
    }
    return result;
};

console.log(sumOfSquares([2, 3, 5]));

Functional style

var sumOfSquares = pipe(map(square), reduce(add, 0));

console.log(sumOfSquares([2, 3, 5]));

Functional Programming in Javascript

With first-class function, closures, and anonymous functions, Javascript allows us to do a great deal of functional programming, even if we don't have things like pattern matching and homoiconicity. There are some tools built in to modern Javascript environments, and it's straightforward to roll your own.

For the remainder of this talk, we will use the Ramda library that Michael Hurley and I have been developing. But there are a number of interesting alternatives available:

allong.es is a fairly new functional combinators and decorators library
Lemonad is a general-purpose functional programming library
Lazy and Lz are libraries for lazy list processing
Underscore and its more performant clone, Lo-Dash, are general utility libraries with a number of functional capabilities
Functional Javascript, although perhaps outdated today, was the very first successful functional programming library for Javascript

Using Functional Techniques in Javacript

We will approach functional programming by converting an imperative example into a functional one.

We will also briefly examine an object-oriented approach, but we'll see that the code that we would like to address is very similar to the imperative one, just organized differently.

Our example will be a Task List application, fetching something like the following data from the server:

var data = {
    result: "SUCCESS",
    interfaceVersion: "1.0.3",
    requested: "10/17/2013 15:31:20".
    lastUpdated: "10/16/2013 10:52:39",
    tasks: [
        {id: 104, complete: false, priority: "high",           dueDate: "11/29/2013",
                  member: "Scott", title: "Do something",      created: "9/22/2013"},
        {id: 105, complete: false, priority: "medium",         dueDate: "11/22/2013",
                  member: "Lena",  title: "Do something else", created: "9/22/2013"},
        {id: 107, complete: true,  priority: "high",           dueDate: "11/22/2013",
                  member: "Mike",  title: "Fix the foo",       created: "9/22/2013"},
        {id: 108, complete: false, priority: "low",            dueDate: "11/15/2013",
                  member: "Punam", title: "Adjust the bar",    created: "9/25/2013"},
        {id: 110, complete: false, priority: "medium",         dueDate: "11/15/2013",
                  member: "Scott", title: "Rename everything", created: "10/2/2013"},
        {id: 112, complete: true,  priority: "high",           dueDate: "11/27/2013",
                  member: "Lena",  title: "Alter all quuxes",  created: "10/5/2013"}
        // , ...
    ]
};

Our Goal

tasks: [
    {id: 104, complete: false, priority: "high",           dueDate: "11/29/2013",
              member: "Scott", title: "Do something",      created: "9/22/2013"},
    {id: 105, complete: false, priority: "medium",         dueDate: "11/22/2013",
              member: "Lena",  title: "Do something else", created: "9/22/2013"},
    // , ...
]

The goal will be a function that accepts a `member` parameter, then fetches the data from the server (or from some application cache), chooses the tasks for that member that are not complete, returns their ids, priorities, titles, and dues dates, sorted by due date.

Since the fetch from the server will likely be asynchronous, we'll hook everything together with promises, and our function will return a promise that should resolve to an array of objects with the required properties.

For our illustrative purposes, we will ignore all error-checking concerns. Obviously in a production system, we would need to consider server-side failures, and bad data scenarios.

Sample Imperative Approach

var getIncompleteTaskSummariesForMember_imperative = function(memberName) {
    return fetchData()
        .then(function(data) {
            return data.tasks;
        })
        .then(function(tasks) {
            var results = [];
            for (var i = 0, len = tasks.length; i < len; i++) {
                if (tasks[i].member == memberName) {
                    results.push(tasks[i]);
                }
            }
            return results;
        })
        .then(function(tasks) {
            var results = [];
            for (var i = 0, len = tasks.length; i < len; i++) {
                if (!tasks[i].complete) {
                    results.push(tasks[i]);
                }
            }
            return results;
        })

(continued on the next slide.)

Sample Imperative Approach (continued)

        .then(function(tasks) {
            var results = [], task;
            for (var i = 0, len = tasks.length; i < len; i++) {
                task = tasks[i];
                results.push({
                    id: task.id,
                    dueDate: task.dueDate,
                    title: task.title,
                    priority: task.priority
                })
            }
            return results;
        })
        .then(function(tasks) {
            tasks.sort(function(first, second) {
                return first.dueDate - second.dueDate;
            });
            return tasks;
        });
};

Similar Object-Oriented Approach

 // main method
var getIncompleteTaskSummariesForMember_objectOriented = function(memberName) {
    return fetchData()
        .then(function(data) {
            var taskList = new TaskList(data.tasks);
            taskList.chooseByMember(memberName);
            taskList.chooseByCompletion(false);
            var newTaskList = taskList.getSummaries();
            newTaskList.sort(new TaskListSorter("dueDate"));
            return newTaskList.tasks;
        });
};

(continued on the next slide.)

Object-Oriented Approach (continued)

var TaskList = (function() {
    var TaskList = function(/*Task[]*/ tasks) {
        this.tasks = tasks;
    };
    TaskList.prototype.chooseByMember = function(memberName) {
        var results = [];
        for (var i = 0, len = this.tasks.length; i < len; i++) {
            if (this.tasks[i].member === memberName) {
                results.push(this.tasks[i]);
            }
        }
        this.tasks = results;
    };
    TaskList.prototype.chooseByCompletion = function(completion) {
        var results = [];
        for (var i = 0, len = this.tasks.length; i < len; i++) {
            if (this.tasks[i].complete == completion) {
                results.push(this.tasks[i]);
            }
        }
        this.tasks = results;
    };

Object-Oriented Approach (continued)

TaskList.prototype.getSummaries = function() {
        var results = [], task;
        for (var i = 0, len = this.tasks.length; i < len; i++) {
            task = this.tasks[i];
            results.push({
                id: task.id,
                dueDate: task.dueDate,
                title: task.title,
                priority: task.priority
            })
        }
        return new TaskList(results);
    };

    TaskList.prototype.sort = function(/*TaskListSorter*/ sorter) {
        this.tasks.sort(sorter.getSortFunction());
    };

    return TaskList;
}());

(continued on the next slide.)

Object-Oriented Approach (continued)

var TaskListSorter = (function()  {
    var TaskListSorter = function(propName) {
        this.propName = propName;
    };
    TaskListSorter.prototype.getSortFunction = function() {
        var propName = this.propName;
        return function(first, second) {
            return first[propName] < second[propName] ? -1 :
                   first[propName] > second[propName] ? +1 : 0;
        }
    };

    return TaskListSorter;
}());

We could continue by defining Task and MinimalTask, but that's probably overkill in Javascript.

It's important for our point to note that the difference between the plain imperative code and the Object-Oriented code, outside a number of `this` keywords, is mostly just organization. The contents of the functions are much the same; it's the way they are organized that varies.

This means that for our purposes, we can focus on the slightly simpler imperative code.

Converting to Functional Code

The process for the remainder of this talk will be to convert this code into concise, readable, functional code, one block at a time, explaining some of the basic building blocks of functional programming as we go. First up is this little function:

.then(function(data) {
    return data.tasks;
})

Functional Version

.then(get('tasks'))

So the obvious question, then, is, what is the get function?

The `get` Function

This is the definition of the get function in the Ramda library:

var get = curry(function(prop, obj) {return obj[prop];});

Ignoring the curry wrapper, this is pretty simple. get (which also goes by the alias of prop) is a function which accepts a property name and an object, and returns the property of the object with that name.

Our then call needs a function, so curry must be doing something interesting with this function, which should return an object propery, so that it insteads returns a new function. We need to take a detour to discuss curry a bit.

Curry

Very sorry, no delicious spicy food here.

Currying Functions

Currying is the process of converting functions that take multiple arguments into ones that, when supplied fewer arguments, return new functions that accept the remaining ones.

var add = curry(function(a, b) {return a + b;});

var add42 = add(42);

console.log(add42(10)); //=> 52
console.log(add42(7)); // 49

Back to `get`

Remember the definition of get:

var get = curry(function(prop, obj) {return obj[prop];});

Now that we understand curry, we can see that a manually curried version of this function might look like this:

var get = function(prop) {
    return function(obj) {
        return obj[prop];
    };
};

And that means that our new get('tasks') is equivalent to

function(obj) {
    return obj['tasks'];
}

Filtering

So far, we've been able to replace this block:

.then(function(data) {
    return data.tasks;
})

with this one:

.then(get('tasks'))

The next block to replace looks like this:

.then(function(tasks) {
    var results = [];
    for (var i = 0, len = tasks.length; i < len; i++) {
        if (tasks[i].member == memberName) {
            results.push(tasks[i]);
        }
    }
    return results;
})

What we're doing is running a filter on the input list, keeping only those that have the correct member property. Let's see how we would do this in a functional paradigm.

Functional Filtering

Many functional libraries come with a filter function, which accepts a predicate function and a list, and returns a new list consisting of those elements of the original list for which the predicate function returns true.

Ramda has one, called filter, and like pretty much every function of more than one parameter, it's curried, with the signature, filter(predicate, list).

Remembering that the then block will pass the list of tasks to us, we really want to call filter with a predicate, getting back a curried function that will accept a list.

Here's a first pass:

.then(filter(function(task) {
    return task.member == memberName;
}))

(Remember that memberName was a parameter to our original function.)

Focused Code

So, for one thing, we've reduced the weight of our custom code:

Original code

.then(function(tasks) {
    var results = [];
    for (var i = 0, len = tasks.length; i < len; i++) {
        if (tasks[i].member == memberName) {
            results.push(tasks[i]);
        }
    }
    return results;
})

Functional version

.then(filter(function(task) {
    return task.member == memberName;
}))

But we've done something more important too: We've moved the focus from iteration and updating the state of a local collection to the real point of this block: choosing the tasks with the proper member property.

One of the most important features of functional programming is that it makes it easy to shift focus in this manner.

Rejecting elements

The next block is similar, except that instead of using filter, we will use reject, which behaves exactly the same except that it chooses those members of the list that don't match the predicate. We replace this code:

.then(function(tasks) {
    var results = [];
    for (var i = 0, len = tasks.length; i < len; i++) {
        if (!tasks[i].complete) {
            results.push(tasks[i]);
        }
    }
    return results;
})

with this:

.then(reject(function(task) {
    return task.complete === true;
)))

Refactoring... already

A reasonable question would be why with didn't do this instead, which would work equally well:

.then(filter(function(task) {
    return task.complete !== true;
))

The reason is that the similarity between these two blocks will offer us a chance to refactor our code into something still more descriptive:

function(task) {
    return task.member == memberName;
}

function(task) {
    return task.complete === true;
)

Both of these functions accept an object and return a boolean that describes whether a particular property of the object has a given value. Perhaps a good name for a function that generates such functions would be propMatches. Let's implement that.

Implementing `propMatches`

Simplest Approach

var propMatches = function(prop, val) {
    return function(obj) {
        return obj[prop] === val;
    };
}
// ...
.then(reject(propMatches("complete", true)));

This works, and we could leave it there, but we're going to take another detour into a popular style of functional programming known as points-free coding.

The name has nothing to do with '.' characters. It derives from mathematics and has something to do with homomorphisms on topological spaces.

This won't be on the test.

Points-free definitions

With the functions add (which adds two numbers) and reduce (which runs the supplied function against an accumulator and each element of the list, feeding the result of each call into the next one and returning the final result), we can easily define a sum function like this:

var sum = function(list) {
    return reduce(add, 0, list);
};

Because of the automatic currying, though, the following is entirely equivalent:

var sum = reduce(add, 0);

This is the points-free style, defining functions without ever making direct reference to their arguments.

There are plenty of ~~arguments in favor of it~~, plenty of ~~points to support it~~, reasons to like it, but the most important one might just be the simplicity. There is a great deal to be said for elegant, readable code.

A points-free version of `propMatches`

Can we redefine the following in a points-free style?

var propMatches = function(prop, val) {
    return function(obj) {
        return obj[prop] === val;
    };
}

Here's a version that is closer to points-free:

var propMatches = function(prop, val) {
    return compose(eq(val), get(prop));
}

Huh? What? compose? eq?

eq is easy: like all good functions of multiple parameters, it's curried, and it simply reports whether its two arguments are equal. So eq(val) is a function which reports whether its parameter has the same value as does val. But now we need to discuss compose.

Functional composition

I have another short talk dedicated entirely to techniques of functional composition. This is a very brief overview:

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

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

Ramda also defines pipe, which does much the same thing, but runs the functions in the opposite order. So pipe(add1, square)(x) equals square(add1(x)). Both styles have their uses.

Back to `propMatches`

So now this definition makes sense:

var propMatches = function(prop, val) {
    return pipe(get(prop), eq(val));
}

Switching from compose to pipe gives us a further way to clean it up, and make it entirely points-free, using a useful feature of Ramda we haven't seen implemented in other libraries, which we call (for now) use-over. Used like use(func).over(transformer1, ... transformerN), this returns a function which accepts N parameters, feeds them to the respective transformers, and then calls func using the results of all these. This gives us the final version of propMatches:

var propMatches = use(pipe).over(get, eq);

Using our new function

This function seems quite useful, and we might want to fold it into Ramda one day, but it's not there now. Still, all these explanations aside, it was only a minute or two of work to do this refactoring and arrive at a fairly simple version of propMatches. We would plug it back in like this:

var propMatches = use(pipe).over(get, eq);

// ...

.then(filter(propMatches('member', memberName)))
.then(reject(propMatches('complete', true)))

New objects from old

The next block we wanted to update looked like this:

.then(function(tasks) {
    var results = [], task;
    for (var i = 0, len = tasks.length; i < len; i++) {
        task = tasks[i];
        results.push({
            id: task.id,
            dueDate: task.dueDate,
            title: task.title,
            priority: task.priority
        })
    }
    return results;
})

Functional version:

.then(map(pick(['id', 'dueDate', 'title', 'priority'])))

You're a smart bunch, right? I probably don't even have to explain what pick does, right?

Good, then we can move on to discuss map.

The `map` function

It is not down in any map; true places never are. – Herman Melville

One of the most fundamental functions used in FP is map, which is used to convert one list into a related one by running the same function against each member.

var fiveSquares = map(square, [1, 2, 3, 4, 5]); // => [1, 4, 9, 16, 25];

var shouts = map(toUpperCase, ["oy", "vey"]); //=> ["OY", "VEY"]

There isn't much more to say about map, but it's important to point out that this function and reduce, which we mentioned briefly earlier, are among the most important functional programming tools around.

Partial clones of our objects.

We used map like this:

.then(map(pick(['id', 'dueDate', 'title', 'priority'])))

The magic of currying is again at work here:

pick accepts a list of properties and an object and return a partial clone, copying those properties from the original. Since we just pass in the properties, this curried function returns a new function that accepts an object and returns that partial clone.
map accepts a function and a list an applies the function to the list. But because it's curried, and because we supply only the function generated by the curried pick, this one also returns a new function which will accept a list and create these partial clones of each element in the list.
This function is passed to then, which will simply pass along its parameter (whenever that becomes ready) to our function and "return" the result of running our function against it. (We simply know because of the way prior calls have been built that this will be a list of tasks.)

A final task of some `sort`

The last segment we wanted to convert looked like this:

.then(function(tasks) {
    tasks.sort(function(first, second) {
        return first.dueDate - second.dueDate;
    });
    return tasks;
});

We won't discuss the implementation of sortBy, but the basic idea is that it returns a new list made from an old one by sorting the elements according to keys generated by the function passed to it. For instance:

sortBy(function(person) {
    return person.lastName + "," + person.firstName;
}, people);

Again with the `curry`

Again, we take advantage of the fact that our important functions are curried, and use get('dueDate'). This creates a function that, fed one of our task objects, returns its due date. We can feed this into sortBy to get the following:

.then(sortBy(get('dueDate')))

While this is not a lot less code than the original:

.then(function(tasks) {
    tasks.sort(function(first, second) {
        return first.dueDate - second.dueDate;
    });
    return tasks;
});

it clearly is a savings. However, much more importantly, the code is all clearly aimed at our problem. The new code is much closer to a direct translation of the English specifications than is the original.

Recap – Imperative

var getIncompleteTaskSummariesForMember_imperative = function(memberName) {
    return fetchData()
        .then(function(data) {
            return data.tasks;
        })
        .then(function(tasks) {
            var results = [];
            for (var i = 0, len = tasks.length; i < len; i++) {
                if (tasks[i].member == memberName) {
                    results.push(tasks[i]);
                }
            }
            return results;
        })
        .then(function(tasks) {
            var results = [];
            for (var i = 0, len = tasks.length; i < len; i++) {
                if (!tasks[i].complete) {
                    results.push(tasks[i]);
                }
            }
            return results;
        })
        .then(function(tasks) {
            var results = [], task;
            for (var i = 0, len = tasks.length; i < len; i++) {
                task = tasks[i];
                results.push({
                    id: task.id,
                    dueDate: task.dueDate,
                    title: task.title,
                    priority: task.priority
                })
            }
            return results;
        })
        .then(function(tasks) {
            tasks.sort(function(first, second) {
                return first.dueDate - second.dueDate;
            });
            return tasks;
        });

Recap – Functional

var propMatches = use(pipe).over(get, eq); // TODO: move to library?

var getIncompleteTaskSummariesForMember_functional = function(memberName) {
    return fetchData()
        .then(get('tasks'))
        .then(filter(propMatches('member', memberName)))
        .then(reject(propMatches('complete', true)))
        .then(map(pick(['id', 'dueDate', 'title', 'priority'])))
        .then(sortBy(get('dueDate')));
};

OO makes code understandable by encapsulating moving parts. FP makes code understandable by minimizing moving parts.

Not the Library

It's important to note that nothing in here is meant to promote the Ramda library in particular.

While I'm certainly partial to it, the only thing that we used in here that was not entirely common to the majority of functional programming libraries (across many languages, in fact) was the use().over() construct, and all that really gained us was to turn a short function into a points-free one-liner.

Certain libraries make things easier than others, though. The equivalent code using Underscore or LoDash, which don't curry their functions by default, and which choose a different default parameter order, would involve significantly more boilerplate.

Most Important Functions

We've seen what are probably the most important functions in functional programming:

curry
compose
map
reduce
filter

There's one that to some might be conspicuous by it's absence:

forEach

I would argue that this is not actually appropriate to functional programming, as its main purpose is to help you achieve side-effects. But many libraries do include one.

What We Gain from FP Style

Elegance and simplicity

And through this, we also can achieve

Straightforward unit testing
Easier debugging
Simple concurrency

Functional Programming

Scott Sauyet

An Overview of Functional Techniques (for non FP'ers) using Javascript

Agenda

What is Functional Programming?

No Single Definition

Chief difference between OOP and FP

Object-Oriented

Functional

What does this mean in the business environment?

Are you sure?

How much business logic is written like this?

Declarative vs Imperative Programming

Imperative style

Functional style

Functional Programming in Javascript

Using Functional Techniques in Javacript

Our Goal

Sample Imperative Approach

Sample Imperative Approach (continued)

Similar Object-Oriented Approach

Object-Oriented Approach (continued)

Object-Oriented Approach (continued)

Object-Oriented Approach (continued)

Converting to Functional Code

Functional Version

The get Function

Curry

Very sorry, no delicious spicy food here.

Currying Functions

Back to get

Filtering

Functional Filtering

Focused Code

Original code

Functional version

Rejecting elements

Refactoring... already

Implementing propMatches

Simplest Approach

Points-free definitions

A points-free version of propMatches

Functional composition

Simplest Implementation

Back to propMatches

Using our new function

New objects from old

Functional version:

The map function

Partial clones of our objects.

A final task of some sort

Again with the curry

Recap – Imperative

Recap – Functional

Not the Library

Most Important Functions

What We Gain from FP Style

Questions?

An Overview of Functional Techniques
(for non FP'ers) using Javascript

The `get` Function

Back to `get`

Implementing `propMatches`

A points-free version of `propMatches`

Back to `propMatches`

The `map` function

A final task of some `sort`

Again with the `curry`