Functional programming is less about patterns and more about laws. Laws allow the programmer to reason about their programs like a mathematician can reason about an equation.
Let's look at adding numbers. Adding is a binary operation (it takes two numbers) and always produces another number.
1 + 2 = 3
2 + 1 = 3
1 + (2 + 3) = 6
(1 + 2) + 3 = 6
((1 + 2) + 3) + 4 = 10
(1 + 2) + (3 + 4) = 10
1 + (2 + 3) + 4 = 10
1 + (2 + (3 + 4)) = 10
We can add numbers in any order and still get the same result. This property is associativity and it forms the basis of the associative law.
Adding zero is somewhat interesting, or taken for granted.
1 + 0 = 1
0 + 1 = 1
3 + 0 = 3
0 + 3 = 3
Adding zero to any number will not change the number. This is known as the identity element.
These two things, (1) an associative binary operation and (2) an identity element, make up a monoid.
If we can ...
- encode your predicates as elements of a domain
- create a binary operation for the elements
- determine the identity element
... then we receive the benefits of belonging to the monoid category, allowing us to reason about our program in an equational way. There's no pattern to learn, only laws to uphold.
1. Making a domain
Getting your data right is tricky, even more so in a multi-paradigm language like JavaScript. This question is about functional programming though so functions would be a good go-to.
In your program ...
build() {
var fnPredicate = (p) => true;
if (typeof config.minIncome == 'number') {
fnPredicate = (p) => fnPredicate(p) && config.minIncome <= p.income;
}
if (typeof config.member == 'boolean') {
fnPredicate = (p) => fnPredicate(p) && config.member === p.member;
}
// .. continue to support more predicateparts.
},
... we see a mixture of the program level and the data level. This program is hard-coded to understand only an input that may have these specific keys (minIncome, member) and their respective types (number and boolean), as well the comparison operation used to determine the predicate.
Let's keep it really simple. Let's take a static predicate
item.name === "Sally"
If I wanted this same predicate but compared using a different item, I would wrap this expression in a function and make item a parameter of the function.
const nameIsSally = item =>
item.name === "Sally"
console .log
( nameIsSally ({ name: "Alice" }) // false
, nameIsSally ({ name: "Sally" }) // true
, nameIsSally ({ name: "NotSally" }) // false
, nameIsSally ({}) // false
)
This predicate is easy to use, but it only works to check for the name Sally. We repeat the process by wrapping the expression in a function and make name a parameter of the function. This general technique is called abstraction and it's used all the time in functional programming.
const nameIs = name => item =>
item.name === name
const nameIsSally =
nameIs ("Sally")
const nameIsAlice =
nameIs ("Alice")
console .log
( nameIsSally ({ name: "Alice" }) // false
, nameIsSally ({ name: "Sally" }) // true
, nameIsAlice ({ name: "Alice" }) // true
, nameIsAlice ({ name: "Sally" }) // false
)
As you can see, it doesn't matter that the expression we wrapped was already a function. JavaScript has first-class support for functions, which means they can be treated as values. Programs that return a function or receive a function as input are called higher-order functions.
Above, our predicates are represented as functions which take a value of any type (a) and produce a boolean. We will denote this as a -> Boolean. So each predicate is an element of our domain, and that domain is all functions a -> Boolean.
2. The Binary Operation
We'll do the exercise of abstraction one more time. Let's take a static combined predicate expression.
p1 (item) && p2 (item)
I can re-use this expression for other items by wrapping it in a function and making item a parameter of the function.
const bothPredicates = item =>
p1 (item) && p2 (item)
But we want to be able to combine any predicates. Again, we wrap the expression we want to re-use in an function then assign parameter(s) for the variable(s), this time for p1 and p2.
const and = (p1, p2) => item =>
p1 (item) && p2 (item)
Before we move on, let's check our domain and ensure our binary operation and is correct. The binary operation must:
- take as input two (2) elements from our domain (
a -> Boolean)
- return as output an element of our domain
- the operation must be associative: f(a,b) == f(b,a)
Indeed, and accepts two elements of our domain p1 and p2. The return value is item => ... which is a function receiving an item and returns p1 (item) && p2 (item). Each is a predicate that accepts a single value and returns a Boolean. This simplifies to Boolean && Boolean which we know is another Boolean. To summarize, and takes two predicates and returns a new predicate, which is precisely what the binary operation must do.
const and = (p1, p2) => item =>
p1 (item) && p2 (item)
const nameIs = x => item =>
item.name === x
const minIncome = x => item =>
x <= item.income
const query =
and
( nameIs ("Alice")
, minIncome (5)
)
console .log
( query ({ name: "Sally", income: 3}) // false
, query ({ name: "Alice", income: 3 }) // false
, query ({ name: "Alice", income: 7 }) // true
)
3. The Identity Element
The identity element, when added to any other element, must not change the element. So for any predicate p and the predicate identity element empty, the following must hold
and (p, empty) == p
and (empty, p) == p
We can represent the empty predicate as a function that takes any element and always returns true.
const and = (p1, p2) => item =>
p1 (item) && p2 (item)
const empty = item =>
true
const p = x =>
x > 5
console .log
( and (p, empty) (3) === p (3) // true
, and (empty, p) (3) === p (3) // true
)
Power of Laws
Now that we have a binary operation and an identity element, we can combine an arbitrary amount of predicates. We define sum which plugs our monoid directly into reduce.
// --- predicate monoid ---
const and = (p1, p2) => item =>
p1 (item) && p2 (item)
const empty = item =>
true
const sum = (...predicates) =>
predicates .reduce (and, empty) // [1,2,3,4] .reduce (add, 0)
// --- individual predicates ---
const nameIs = x => item =>
item.name === x
const minIncome = x => item =>
x <= item.income
const isTeenager = item =>
item.age > 12 && item.age < 20
// --- demo ---
const query =
sum
( nameIs ("Alice")
, minIncome (5)
, isTeenager
)
console .log
( query ({ name: "Sally", income: 8, age: 14 }) // false
, query ({ name: "Alice", income: 3, age: 21 }) // false
, query ({ name: "Alice", income: 7, age: 29 }) // false
, query ({ name: "Alice", income: 9, age: 17 }) // true
)
The empty sum predicate still returns a valid result. This is like the empty query that matches all results.
const query =
sum ()
console .log
( query ({ foo: "bar" }) // true
)
Free Convenience
Using functions to encode our predicates makes them useful in other ways too. If you have an array of items, you could use a predicate p directly in .find or .filter. Of course this is true for predicates created using and and sum too.
const p =
sum (pred1, pred2, pred3, ...)
const items =
[ { name: "Alice" ... }
, { name: "Sally" ... }
]
const firstMatch =
items .find (p)
const allMatches =
items .filter (p)
Make it a Module
You don't want to define globals like add and sum and empty. When you package this code, use a module of some sort.
// Predicate.js
const add = ...
const empty = ...
const sum = ...
const Predicate =
{ add, empty, sum }
export default Predicate
When you use it
import { sum } from './Predicate'
const query =
sum (...)
const result =
arrayOfPersons .filter (query)
Quiz
Notice the similarity between our predicate identity element and the identity element for &&
T && ? == T
? && T == T
F && ? == F
? && F == F
We can replace all ? above with T and the equations will hold. Below, what do you think the identity element is for ||?
T || ? == T
? || T == T
F || ? == F
? || F == F
What's the identity element for *, binary multiplication?
n * ? = n
? * n = n
How about the identity element for arrays or lists?
concat (l, ?) == l
concat (?, l) == l
Having Fun?
I think you'll enjoy contravariant functors. In the same arena, transducers. There's a demo showing how to build a higher-level API around these low-level modules too.
