1 About this document

This document is intended as a kind of a guide to functional programming techniques. There are code examples and explanations for function composition, currying, partial application, map/filter/reduce and more. It uses JavaScript mostly, but it also presents LiveScript to show the difference between using FP techniques with and without syntactic support.

I think the target group are experienced JavaScript programmers, who already use some FP patterns, but would like to learn more about how they work or to learn more such patterns.

All the examples are self contained and they can all be pasted into the REPL or empty file and directly executed (you need to npm install used libraries tough). The results of each example are displayed below it and they are being recomputed automatically on every export, thanks to Org Babel mode, to ensure that they are always correct.

It's a work in progress and only covers basics right now. I'm going to gradually extend it with new concepts and examples. Any help in this is greatly appreciated.

2 Example of imperative vs. declarative

Do not try to understand exactly what's happening here - these examples are here just to give you a taste of what declarative or functional style looks like on the surface. It's mostly easy to discern such code by its outer structure, even without going into details.

Anyway, the problem: "we have a list of user objects, and we want to get a list of full names." Pretty straightforward. Let's see the difference between imperative and functional approaches to this problem.

2.1 imperative

The first example is a completely standard implementation. Currently, most programmers would write it like this.

var result = [];

objs = [
  {firstName: "barney", lastName: "Rubble"},
  {firstName: "fred", lastName: "Flinstone"}
];

for(var i=0, len=objs.length; i<len; i++) {
  var fname = objs[i].firstName,
      lname = objs[i].lastName;

  result.push(fname + " " + lname);
}

console.log(result);
barney Rubble fred Flinstone

Nothing fancy, and it works.

2.2 declarative

Second example does exactly the same thing, but looks differently. It's because there's nothing done (no computation) until the very last line: instead of actually executing the steps of an algorithm we merely define what we want in terms of parts, which we combine together.

var juxt = require("mori").juxt;
var _ = require("ramda");

// first, we define a function which will get us both parts of a name
var getNameParts = juxt(_.prop("firstName"),
                        _.prop("lastName"));

// we also need a function which will join the parts with a space together
var joinNameParts = _.join(" ");

// and lastly, we define a function which will apply the two functions above
// to every element of some collection
var getFullNames = _.map(_.compose(joinNameParts,
                                   getNameParts));

users = [
  {firstName: "barney", lastName: "Rubble"},
  {firstName: "fred", lastName: "Flinstone"}
];

// finally we apply the resulting function to get our result
console.log(getFullNames(users));
barney Rubble fred Flinstone

3 The very basics of FP

We're going to try to dissect some of the mechanisms used in a previous example. We'll start from the most basic principles and then go through more advanced concepts.

One very important concept is that of a HOF, which stands for "higher-order function". It means a function which either accepts other functions as arguments or return some function as a result (or does both).

3.1 compose

Composing functions is a fundamental tool in FP. The `compose` HOF, which is responsible for this, takes a couple of functions, and returns a new, composed one. When calling composed function it first calls last of the functions with given arguments, then calls second to last function passing it results of the previous one and so on.

var R = require("ramda");
var triple = function(x) { return x * 3; };
var double = function(x) { return x * 2; };
var square = function(x) { return x * x; };

var composed = R.compose(triple, double, square);

console.log(
  composed(5) == triple(double(square(5)))
);
true

One thing worth noting here is that composition works just like addition in maths, which means all three expressions below mean the same thing:

compose(compose(f, g), h)
compose(f, compose(g, h))
compose(f, g, h)

Because function composition is so important, LiveScript provides not one, but three syntactic forms for it.

# `it` is a name of a function single argument when it wasn't named otherwise
triple = -> it * 3
double = -> it * 2
square = -> it * it

# basic form - the dot operator *has* to be surrounded by spaces
composed1 = triple . double . square

# or, to indicate the direction of data flow:
composed2 = triple << double << square

# also possible to make it flow the other direction:
composed3 = square >> double >> triple

console.log composed1(5) == composed2(5) == composed3(5)
true

This makes composing functions very cheap in terms of syntactic overhead, which in turn makes using it more natural and easier in LiveScript programs. Still, this is merely a "sugar" - you can get exactly the same semantics in JavaScript with a normal `compose` function.

3.2 curry

Just like `compose`, `curry` function is essential for FP and is a basis of most of FP techniques. It is a technique of creating functions which accept multiple arguments in systems, where it's only allowed for a function to take a single parameter.

It can be also used the other way around: in our case we're more interested in transforming one function which takes multiple arguments into a series of functions taking a single one.

var R = require("ramda");

var addFourNumbers = function(a, b, c, d) {return a + b + c + d;};
var curriedAddFourNumbers = R.curry(addFourNumbers);

// now we can call curriedAddFourNumbers in a couple of different ways
var f = curriedAddFourNumbers; // let's give it a shorter name for convenience

console.log(
  addFourNumbers(1, 2, 3, 4),
  f(1, 2, 3, 4),
  f(1)(2)(3)(4),
  f(1, 2, 3)(4),
  f(1)(2, 3, 4)
);
10 10 10 10 10

This is very useful when we want to provide some arguments to a function in one place and then only pass remaining arguments later, at a ultimate call site.

Like with `compose`, LiveScript provides syntactic support for currying - there's no dedicated syntax for transforming an existing function into a curried one, but there is a neat shortcut for defining new functions which are curried from the start.

# all you have to do to create a curried function is to use "long arrow"
prependTo = (lst, el) -->
    lst.unshift(el)

even-nums = []
odd-nums = []

even = prependTo(even-nums)
odd = prependTo(odd-nums)

for i from 1 to 10
    switch (i %% 2 == 0)
    | true  => even(i)
    | false => odd(i)

console.log even-nums, odd-nums
[ 10, 8, 6, 4, 2 ] [ 9, 7, 5, 3, 1 ]

Still, if you need to work with functions not of your own making, even in LiveScript you need to use a HOF, like the one Ramda provides.

3.3 partial

Partial application is a way of supplying some arguments for a function beforehand, which is similar to what currying does. However, partial application differs from currying in that it's always only one level deep: when using it you get a function which you have to call with all the remaining (not specified when partially applying) arguments at once.

var R = require("ramda");
var greet = function(salutation, title, firstName, lastName) {
   return salutation + ', ' + title + ' ' + firstName + ' ' + lastName + '!';
};

var sayHello = R.partial(greet, 'Hello');
var sayHelloToMs = R.partial(sayHello, 'Ms.');

console.log(
  sayHelloToMs('Jane', 'Doe')
);

// the difference from currying is that this:
console.log(
  sayHelloToMs('Jane')
);
// returns just a value, not another function, which would be the case with
// currying
H, e l l!
H, e l l!
undefined

As you probably guessed already, LiveScript provides syntactic support for partial application too. The problem with partial application based on HOFs is that it's hard to handle arguments in the middle of argument list. This is why, by the way, the function shown above is called `partialRight`; there's also `partial` which fills arguments starting from the other end. In LiveScript that's not necessary, thanks to syntactic sugar.

greet = (salutation, title, firstName, lastName) ->
    salutation + ', ' + title + ' ' + firstName + ' ' + lastName + '!'

sayHelloToJones = greet "Hello", _ , _, "Jones"
console.log sayHelloToJones("Mr.", "Joe")
console.log sayHelloToJones("Mrs", "Jane")
Hello, Mr. Joe Jones!
Hello, Mrs Jane Jones!

Again, having syntactic support for this feature makes its use much more natural and easier, but you can use it with a little effort in plain JS.

3.4 flip

There's one more function that messes with other functions' arguments, called `flip`. Given a function it returns a function which does exactly the same thing, but takes arguments in reverse order. This is useful when combined with currying - sometimes it's easier to flip and curry a function than partially apply it.

var R = require("ramda");

var mergeThree = function(a, b, c) {
  return ([]).concat(a, b, c);
}

console.log(
  mergeThree(1, 2, 3)
);

var flipped = R.flip(mergeThree);

console.log(
  flipped(1, 2, 3)
);
[ 1, 2, 3 ]
[ 2, 1, 3 ]

But the most immediately useful application of `flip` is to reduce syntactic clutter in CoffeeScript and LiveScript! This may seem strange, as both those languages are intended to provide better syntax for JS. But there are cases where a generally nice syntax becomes less convenient. One of such cases is when you need to pass a function as other than last argument to other function.

# all the parens below would be unnecessary if setTimeout would take args in
# different order
setTimeout(
    (->
        doSomething!
        andSomethingElse!),
    400
)

delay = flip(setTimeout)
delay 400, ->
    doSomething!
    andSomethingElse!

4 FP tools for working with collections

"LISP" stands for "LISt Processor", or so they say. In FP-focused systems you very often have a single data structure and myriads of functions (both normal and HOFs) to work with this structure. Historically it was a Linked List but JS `Array` is a good replacement.

4.1 filter

`filter`, sometimes called `select` is used for getting a new collection with only those elements of larger collection that pass some test. It's basically a `for` loop with a nested `if` inside. One advantage of using `filter` is that with it you have no way of making "off by one error", and it also can be shorter while being more descriptive. This is a property of all FP constructs, though.

First, in JavaScript:

// with Underscore/Lo-Dash
var _ = require("lodash");

var evens = _.filter([1, 2, 3, 4, 5, 6], function(num) { return num % 2 == 0; });
// console.log(evens);

var characters = [
  { 'name': 'barney', 'age': 36, 'blocked': false },
  { 'name': 'fred',   'age': 40, 'blocked': true }
];

var youngsters = _.filter(characters, function(x) { return x.age < 40; })
console.log(youngsters);
{ name: barney age: 36 blocked: false }

Of course, LiveScript makes this significantly easier and more convenient:

# with LiveScript syntactic support and Prelude.ls
{filter} = require "prelude-ls"


# special name `it` is a function argument in case it wasn't named otherwise
evens = filter (-> it % 2 == 0), [1, 2, 3, 4, 5, 6]
console.log evens


characters = [
    { 'name': 'barney', 'age': 36, 'blocked': false },
    { 'name': 'fred',   'age': 40, 'blocked': true }
]

# partial application of property access:
youngsters = filter (.age < 40), characters
console.log youngsters
[ 2, 4, 6 ]
[ { name: 'barney', age: 36, blocked: false } ]

…but beware, we can easily go overboard with this syntax (and semantics) and write something like this:

{filter} = require "prelude-ls"
evens = filter (% 2) >> (== 0), [1, 2, 3, 4, 5, 6]
console.log evens
[ 2, 4, 6 ]

…which is decidedly not "easier to read". Like all powerful features, partial application of operators (including dot operator) should be used sparingly and only where it makes sense.

By the way: the last `filter` example is written in a "point-free" style, see wiki page

4.2 map

With `map` you can transform one list into the other of the same length. `map` and `filter` together can replace very many `for` loops in your code. For example, in JavaScript with Ramda:

var R = require("ramda");

var characters = [
  { name: 'barney', age: 36 },
  { name: 'fred',   age: 40 }
];

var names = R.map(R.path(['name']), characters);
console.log(names);
barney fred

In LiveScript, again, partial application of operators (here of property access) comes in handy:

{map} = require "prelude-ls"
characters = [
    { 'name': 'barney', 'age': 36 },
    { 'name': 'fred',   'age': 40 }
]

# again, partial application of property access:
names = map (.name), characters
console.log names
[ 'barney', 'fred' ]

I'm not spending much time on `map` because it's very similar in the way it works to `filter` - it's easy to see a `for` loop behind both of them. The next function, which can be used to implement both map and filter by the way, is more interesting.

4.3 reduce or fold

With reduce (or fold as it's sometimes called) you can express every operation that loops over a collection. `reduce` takes as an argument a function - of course… - some initial value and a collection. It then calls the function with two arguments, passing it initial value and first element of collection. Then it proceeds to call the function with the next element and the result of previous function call. This way you can build arbitrary state while traversing a collection: you can make a return value of your function anything as long as your function can also take this value as an argument.

The most obvious example of using reduce is something like this:

var R = require("ramda");
var numbers = [1, 2, 3];
var add = function(a, b) {
  return a + b;
};

var res = R.reduce(add, 10, numbers);
console.log(res);
16

…but that's not very interesting. Let's see how to build map and filter using fold instead:

{fold} = require "prelude-ls"

map = (fun, coll) -->
    wrapped-fun = (soFar, element) ->
        soFar ++ [fun(element)] # ++ concatenates arrays
    fold wrapped-fun, [], coll

filter = (pred, coll) -->
    wrapped-fun = (soFar, element) ->
        if pred(element)
            soFar ++ [element]
        else
            soFar

    fold wrapped-fun, [], coll


characters = [
    { 'name': 'barney', 'age': 36, 'blocked': false },
    { 'name': 'fred',   'age': 40, 'blocked': true }
]
youngsters = filter (.age < 40), characters
console.log youngsters


characters = [
    { 'name': 'barney', 'age': 36 },
    { 'name': 'fred',   'age': 40 }
]
names = map (.name), characters
console.log names
[ { name: 'barney', age: 36, blocked: false } ]
[ 'barney', 'fred' ]

Folds are interesting, because they tend to work well with the types of collections you wouldn't ever suspect, for example with lazy streams or streams of events. You can't loop over those with normal loops, but because they're compatible with fold you can map them or filter them in exactly the same way you would do it with normal Array. This makes fold a useful abstraction of collection type.

4.4 takeWhile, dropWhile and similar

Sometimes we need to omit some initial elements of a collection without knowing how many of them aren't needed, but being able to say when to stop omitting elements with a simple test. We could do this with filter, but it would be inefficient and possibly wrong.

Inefficient, because filter would scan entire collection, instead of stopping on first occurence of "good" element.

Wrong, because we sometimes need to leave elements very similar the ones we want dropped alone when we see them later in a collection.

With JavaScript and mori, which is a very nice library of generic functions for working with collections, we can do it like this:

var res, mori = require("mori");
a = [0,1,2,3,4,5,6,7,8,9]

res = mori.takeWhile(function(n){return n < 5}, a)
console.log(res);

res = mori.dropWhile(function(n){return n < 5}, a)
console.log(res);
(0 1 2 3 4)
(5 6 7 8 9)

It would look exactly the same way in LiveScript (only much shorter thanks to syntactic support) so I won't repeat it here.

4.5 generating collections out of functions

4.5.1 constantly

var res, mori = require("mori");
// with mori

res = mori.map(mori.constantly("foo"), mori.range(4));
console.log(res);
("foo" "foo" "foo" "foo")

4.5.2 iterate

itarate generates a collection of successive, recursive calls of a function. Given a function f and an initial value x, iterate will return a collection like this:

f(x), f(f(x)), f(f(f(x))), …

This would generate infinite collection, so we need to slice it before displaying.

var res, mori = require("mori");

res = mori.take(15, mori.iterate(mori.inc, 0));
console.log(res);
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14)

With a bit of closure magic we can easilly implement a generic `cycle` function which will generate infinite collection by repeating a collection it gets as an argument. It would be a generalization of this pattern:

{take, iterate} = require "mori"
fun = ->
    switch it
    | "one" => "two"
    | "two" => "one"

console.log take 10, iterate(fun, "one")
("one" "two" "one" "two" "one" "two" "one" "two" "one" "two")

…and is left as an excersise for the reader… :)

Other than that, iterate is useful for hiding or memoizing recursive calls.

4.5.3 repeatedly

Sometimes we need

var res, mori = require("mori");

res = mori.repeatedly(5, Math.random);
console.log(res);
(0.9219275391660631 0.5783372039441019 0.04165388969704509 0.8624316973146051 0.3160739492159337)

5 More FP tools for working with functions

5.1 combining functions

5.1.1 juxt

`juxt` is a function which takes N functions (each taking a single argument) and returns a function, which takes a single argument and returns a list of N values. Schematically:

juxt f, g, ... == (x) -> [f(x), g(x), ...]
# with mori, Prelude.ls
mori = require "mori"
global import require "prelude-ls"

getNames     = mori.juxt (.firstName), (.lastName)
joinParts    = (fold1 (-> &0 + " " + &1))

getFullNames = joinParts << getNames


characters = [
    {'firstName': 'barney',"lastName": "Rubble" 'age': 36, 'blocked': false },
    {'firstName': 'fred',  "lastName": "Flinstone" 'age': 40, 'blocked': true }
]

console.log (map getFullNames, characters)
# => ["barney Rubble", "fred Flinstone"]

# how to make sure both first and last names are capitalized?
getFullNames = joinParts << (map capitalize) << getNames

console.log (map getFullNames, characters)
# => ["Barney Rubble", "Fred Flinstone"]
[ 'barney Rubble', 'fred Flinstone' ]
[ 'Barney Rubble', 'Fred Flinstone' ]

5.1.2 pipeline

Some libraries provide a variation of `compose`, which takes arguments in a different order, and which immediately calls the resulting function. Its first argument is actually a value that will be passed to the composed function.

It's useful when you have a sequence of operations which only makes sense for a given value. Looks like this:

// with mori
var _ = require("mori");

console.log(
  _.pipeline(
    _.vector(1,2,3),
    _.curry(_.conj, 4),
    _.curry(_.conj, 5)
  )
);
1 2 3 4 5

Of course, LiveScript has syntactic support for pipelines too:

{map, capitalize} = require "prelude-ls"
value = [1, 2, 3] |> map ('no. ' +) |> map capitalize
console.log value
[ 'No. 1', 'No. 2', 'No. 3' ]

***org trampoline

function trampoline(fun) {
  return function (arg) {
    var fn = fun(arg);
    while(fn && typeof fn === 'function'){
      fn = fn();
    }
    return fn
  }
}

function count(arr) {
  var el = 1;
  var n = 0, i = 0;
  var doCount = function () {
    if(arr[i++] == el) n++;
    return i < arr.length ? doCount : n;
  }
  return doCount;
}

console.log(trampoline(count)([1, 2, 1, 1, 3]) == 3);
true

5.2 MORE TO COME

5.2.1 promises

5.2.2 more function utilities (once, throttle, debounce)

5.2.3 wrap, before, after - decorating funcions

5.2.4 Kestrel and Thrush combinators (KaTy.js)

Author: "Piotr Klibert"

Created: 2017-04-11 wto 23:30

Validate