X-Team Blog - The Most-Loved Company for Engineers

Functional Programming: Composition and Associativity

Written by Joseph Rex | Dec 26, 2017 5:00:00 AM

This article is the continuation of A Functional Programming Primer, where we gently introduced the concept of functional programming.

Composition and associativity are more advanced parts of functional programming. It might seem daunting at first, but as we dive further, it gets clearer.

Composition can also be expressed as combination. It shows the directional flow of data in our declaratively written code by combining multiple functions in a hierarchy, passing inputs from right to left. It involves pipelining the output of one function as input to another. Consider the following:

const y = humanize('chuck_norris') // chuck norris
const z = capitalize(y) // Chuck Norris

The humanize and capitalize functions are small and simple. As mentioned in the previous article, loose coupling is one of the building blocks for functional programming, and composition relies on such smaller functions. To compose these functions, let's start by reducing the friction caused by various assignments.

const z = capitalize(humanize('chuck_norris'))

This is a tad better, but if we were to provide this as an API to another developer, it still is very imperative. To get a little more declarative, both functions can be made into one that passes the output of one as input to the other.

function readableName(name){
  return capitalize(humanize(name));
}

const z = readableName('chuck_norris')

The readableName function abstracts the stages of operations, and it takes advantage of tail call optimization — which along with higher-order functions and first-class functions are the reasons why functional programming in JavaScript is possible. The problem, however, is that the readableName function has broken the Law of Demeter by calling functions that were not defined in its scope. This way, we simply can not test readableName without defining humanize and capitalize in our test environment.

Given a sequence of operation here — we want to humanize before capitalize, we can create a reusable utility function. A function that composes smaller functions in their order of enclosure, visible from left-to-right.

const compose = (func1, func2) => {
  return arg => func1(func2(arg))
};

const readableName = compose(capitalize, humanize);

const z = readableName('chuck_norris') // chuck norris -> Chuck Norris

The compose function above returns a lambda (anonymous function) that takes a new argument and runs it through the functions given to compose. By creating this flow of data from one function output to the input of another, it is always better to have some type safety in place or at least be able to predict the datatype that each of the functions returns, to ensure compatibility with any function taking it as input.

An important point to note here is how the arguments are ordered in the compose function. Because the functions would be originally written as:

capitalize(humanize('chuck_norris'))

we pass them as argument in that sequence from left to right.

compose(capitalize, humanize)

When we consider the actual order of execution, this visual sequence might get confusing as we have to humanize the string first to get two separate words, then capitalize each of the words. When the sequence is ordered by the flow of execution, it becomes a pipe.

A pipe function would be used this way:

const pipe = (func1, func2) => {
  return arg => func2(func1(arg))
};

pipe(humanize, capitalize);

Both compose and pipe have different cases where they may be more applicable than the counterpart. They can be found in functional libraries like Ramda and lodash-fp and would work with more than just two factored functions.

/* Ramda */
R.compose(capitalize, humanize)
R.pipe(humanize, capitalize)

/* Lodash-FP */
_.compose(capitalize, humanize)
// OR
_.flowRight(capitalize, humanize)

_.pipe(humanize, capitalize)
// OR
_.flow(humanize, capitalize)

Compose vs Curry

Currying is the transformation of functions with n parameters into a sequence of n unary functions. Where the original function gets n - 1 nested functions.

Tip: A curried function is always unary.

Currying functions take a similar pattern as composition, which often causes them to be mistaken for each other. Here's a simple curry function done with the help of arrow functions

const sum = a => b => a + b
sum(3)(5) // 8

as you might have noticed, that function looks a lot like our compose function from earlier

const compose = (func1, func2) => arg => func1(func2(arg))

A big similarity is that they both eliminate points, but the compose function is binary, and it can be anary. This is because compose pipes a sequence of enlisted functions, while curry allows for partial application with constrained parameters. Despite the distinction, a curried function can achieve some level of composition.

What are points? Points are another way to refer to arguments. Tacit programming or point-free style is a functional approach that lends itself to composition by not identifying inputs as direct function arguments. Using the example we started with,

// not point-free because name argument is acknowledged
const readableName = name => {
  return capitalize(humanize(name))
}

// point-free
const readableName = compose(capitalize, humanize)

Another common use of point-free style is in negated predicates (functions that return true or false).

const isEven = num => num % 2 === 0

to create an isOdd function, we don't have to rewrite the logic; we could simply negate isEven

const isOdd = num => !isEven(num)

If we have to create a few more negated predicate functions, this becomes an unnecessary repetition. The fat arrow syntax makes it compact and not obvious, but we could make this better by creating a negate utility function.

const not => fn => (...args) => !fn(...args) 

Note: A rest parameter is used because we can't always predict the number of argument an input function takes.

With not, the isOdd function can be written with no points.

isOdd = not(isEven)

That was a huge drift on trying to explain point-free style. This is because it's a concept that took me (and many others I've encountered) a while to grasp.

Partial Application

The partial application of functions occurs at the same point where composition occurs. Using the curry example from above again:

const sum = a => b => a + b

we can partially apply this to create a function that adds 5 to any given value:

const add5 = sum(5)
add5(10) // 15

now when we want to create another function that adds 2 to any other given input, we could simply do this

const add2 = sum(2)
add2(10) // 12

add2 as a stand-alone function could also be passed into a map to operate on the items in an array.

[1,2,4,5].map(add2) // [3,4,6,7]

Both add2 and add5 are partially applied functions. A curried function remains partially applied provided its execution times have not met the arity. This means if we had:

const sum = a => b => c => a + b + c

sum(2)(10) // partial applied
sum(2)(10)(4) // 16

executing twice will still give a partially applied function until the arity of 3 is fulfilled.

Associativity

Like many other functional programming concepts, associativity is derived from math. The Associativity property occurs with some binary operations. It is an expression in which the order of evaluation does not affect the end result provided the sequence of the operands does not get changed. Here are some examples

const a = (2 + 4) + 6 // 12
const b = 2 + (4 + 6) // 12
a === b // true

const c = 2 * (4 * 6) // 48
const d = (2 * 4) * 6 // 48
c === d // true

Note: Having 2 + (4 + 6) against (4 + 2) + 6 may still give the same result but it is not associative since the sequence has been changed. This is commutative.

Association is a necessary rule in building monads, and at this point, we are only a step away from working with monads and monoids.