Curry
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.
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.
Is one of these techniques the clear-cut winner in the business world? Is it functional or object-oriented?
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.
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.
We will take a look a brief look at these functional programming features of other languages first, then turn our focus to those things we can actually accomplish in Javascript.
Following an example from Paul Barry we will use the example of the chances of winning a lottery. This calculates the odds of choosing the correct `n` numbers out of the `p` possibilities.
Here is an iterative version of the code:
This is similar, but written recursively:
There are many reasons that functional programmers prefer recursion, but one very simple one is that recursive functions are often much more elegant than their iterative cousins. It's easier to reason about them.
Unfortunately, they often don't perform as well. All the overhead of creating stack contexts for function calls tends to add up. But certain kinds of recursive calls can be easily optimized.
Note that the recursive call in odds1 is the last statement in its branch of the function.
If this is true for all recursive calls, then the function is tail-recursive, and the
compiler can replace the entire set of nested calls with simple JUMP operations.
Such optimizations are required by many functional languages.
This is slated to become required in the next version of the specification for Javascript, but it won't be consistently available client-side for some time.
Some languages make use of an interesting techniqe to define functions: pattern matching. Rather than use
if-blocks in the body of the function, parameter-matching is used to choose which of a collection
of related functions should be called. Here we can see it in Erlang.
Many of us are most familiar with languages that evaluate their expressions as soon as they're encountered. But there are some that wait until the last possible instant. This can have some real benefits.
We'll switch examples here, as there's not much call to do lazy evaluation for lottery odds. We will follow a Haskell example from Chris Eidhof
Note that the right half of quicksort is not calculated in finding the minimum. (Also note the pattern matching here too!)
One very interesting comparison is that lazy evaluation is to the CPU what garbage collection is to memory. The garbage collector allows you to pretend that you have infinite memory; lazy evaluation allows you to pretend that you have infinite processing power.
But there are many reasons to like lazy evaluation. It allows you to operate on theoretically infinite data structures, calculating only those parts you need. And it allows you to define your own efficient control structures inside the language instead of only at the level of the language syntax.
No groaning. At one time you had to learn what polymorphism meant, too!
Homoiconicity has to do with the fact that in some languages, programs are written in a format easily
interpreted also as a data structure. In Scheme, the following is just a quoted list of three items,
define, (square x) (itself a list), and (* x x) (another list)
But the following, which looks almost identical, is a function definition:
LISP-like languages can use this feature to build very powerful domain-specific languages. Many would claim that this is the key feature that has allowed LISP to become the oldest language still in widespread use.
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:
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:
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.
(continued on the next slide.)
(continued on the next slide.)
(continued on the next slide.)
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.
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:
So the obvious question, then, is, what is the get function?
get FunctionThis is the definition of the get function in the Ramda library:
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, to instead returning a new function. So we need to
take a detour to discuss curry a bit.
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.
Different version of currying work slightly differently. In Ramda, you can pass any of the arguments at any time to a curried function. If the total arguments passed have not yet reached the required number, then you will get back a new function. If you reach (or exceed) that number, you will get back the final result.
Some insist that this is not truly currying, but should be called partial application. They
can feel free to call it what they like. It serves the same role as currying does in a more strongly
typed language.
getRemember the definition of get:
Now that we understand curry, we can see that a manually curried version of this function might
look like this:
And that means that our new get('tasks') is equivalent to
So far, we've been able to replace this block:
with this one:
The next block to replace looks like this:
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.
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:
(Remember that memberName was a parameter to our original function.)
So, for one thing, we've reduced the weight of our custom code:
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.
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:
with this:
A reasonable question would be why with didn't do this instead, which would work equally well:
The reason is that the similarity between these two blocks will offer us a chance to refactor our code into something still more descriptive:
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 propEq. Let's implement that.
propEqThis 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.
Don't worry…
This won't be on the test.
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:
Because of the automatic currying, though, the following is entirely equivalent:
This is the points-free style, defining functions without ever making direct reference to their arguments.
There are plenty of 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.
propEqCan we redefine the following in a points-free style?
Here's a version that is closer to points-free, removing the direct reference to obj:
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.
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)).
Note that 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.
propEqSo now this definition makes sense:
Note the switch from compose to pipe.
This 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 propEq:
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 propEq. We would plug it back in like this:
The next block we wanted to update looked like this:
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.
map functionIt 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.
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.
We used map like this:
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.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.)sortThe last segment we wanted to convert looked like this:
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:
curryAgain, 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:
While this is not a lot less code than the original:
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.
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.
We've seen what are probably the most important functions in functional programming:
mapreducefiltercomposecurryThere's one that to some might be conspicuous by it's absence:
forEachI 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.
And through these, we can also achieve
/
#