Menu

Official website

Functional Abstractions In JavaScript: Check Functors Laws

Elty

01 Oct 2018

min read

fp javascript en

JavaScript is a curious mix of programming paradigms. In this post we will focus on the functional traits of JavaScript (JS). In particular we will see how to check that a function satisfies the Functor’s laws.

A Functor[1] is a fundamental abstraction for functional programmers. It behaves like a (very limited) container: you can interact with it only by altering its content.

In the functional community this interface is called map. In the Basic JS arrays offer a map function:

var x = [1, 2, 3]
console.log("Mapping +1: ", x.map((x) => x + 1))
console.log("The original array: ", x)
// $ Mapping +1:  [ 2, 3, 4 ]
// $ The original array:  [ 1, 2, 3 ]

In the following we are going to check if map respects the Functor laws; in other words: is the object array a Functor?

First let’s define a curried[2] fmap to make laws definitions look nice:

const fmap = (fn) => (
    (array) => array.map(fn))

This works as follows:

console.log(fmap((x)=> x+1)([1,2,3]))
// $ [ 2, 3, 4 ]

Then let’s define the two laws that must hold to call something a Functor. The first law says that mapping the identity function on a Functor should produce the same Functor.

The identity function is easy to define:

const id = (x) => x

The first law then becomes:

fmap(id) = id

The second law says that mapping the composition of two functions on a functor should produce the same Functor that is obtained by composing the fmap.

The compose function can be defined as:\

const compose = (fn1,fn2) => (
    (arg) => fn2(fn1(arg)))

The second law then becomes:

fmap( compose(f,g) ) = compose( fmap(f), fmap(g) )

So far we have defined the Functor laws. Now we want to check the JS arrays satisfy them. The Haskell community donated a great tool to test properties of functional software: QuickCheck. We will use the JS implementation of it: jsverify.

In jsverify we can define software properties like the following (from jsverify’s README):

var jsc = require("jsverify");

// forall (f : bool -> bool) (b : bool), f (f (f b)) = f(b).
var boolFnAppliedThrice = jsc.forall("bool -> bool", "bool", function (f, b) {
    return f(f(f(b))) === f(b);
});
console.log(jsc.check(boolFnAppliedThrice));
// $ OK, passed 100 tests
// $ true

As you can see, jsverify generates tests that validate if the property holds. By default it generates 100 tests per property.

Let’s then define our laws as jsverify properties. For this we will need a custom equals function as JS behaves in a peculiar way when comparing empty arrays

console.log([] === [])
// $ false

So our equals will be:

const equals = (x,y) => (JSON.stringify(x) === JSON.stringify(y))

Which behaves as we wish for empty arrays:

console.log(equals([],[]))
// $ true

Now we refine the laws in jsverify format:

var jsc = require("jsverify");
var arrayInt = jsc.array(jsc.integer());

const fmap_law1 = jsc.forall(
    arrayInt,
    (x) =>
    // fmap(id) == id
    equals(
      fmap(id)(x),
      id(x)
    )
);

const fmap_law2 = jsc.forall(
    "integer -> integer",
    "integer -> integer",
     arrayInt,
     (f, g, x) =>
     // fmap( compose(f, g) ) = compose( fmap(f) , fmap(g) )
     equals(
       fmap(compose(f, g))(x),
       compose(fmap(f), fmap(g))(x)
     )
);

Note that here we are applying the curried functions with the input generated by jsverify (i.e., x). And at last we can check our laws hold for an array of integers:

const equals = (x, y) => (JSON.stringify(x) === JSON.stringify(y))
const id = (x) => x
const compose = (fn1, fn2) => (
    (arg) => fn2(fn1(arg))
);
const fmap = (fn) => (
    (array) => array.map(fn)
);

var jsc = require("jsverify");
var arrayInt = jsc.array(jsc.integer());

const fmap_law1 = jsc.forall(
    arrayInt,
    (x) =>
    // fmap(id) == id
    equals(
      fmap(id)(x),
      id(x)
    )
);

const fmap_law2 = jsc.forall(
    "integer -> integer",
    "integer -> integer",
    arrayInt,
    (f,g,x) =>
    // fmap( compose(f, g) ) = compose( fmap(f), fmap(g) )
    equals(
      fmap(compose(f,g))(x),
      compose(fmap(f), fmap(g))(x)
    )
);

console.log("First functor law satisfied?", jsc.check(fmap_law1));
console.log("Second functor law satisfied?", jsc.check(fmap_law2));
// $ OK, passed 100 tests
// $ First functor law satisfied? true
// $ OK, passed 100 tests
// $ Second functor law satisfied? true

So we can be rather confident that JS arrays are Functors! This same approach can be applied to other functional abstractions, but this will be matter of later posts. Hopefully this example will encourage you to learn more about Functors and to start using jsverify.

Good hacking!

[^1]: A more in depth introduction to Functors can be found at

http://learnyouahaskell.com/functors-applicative-functors-and-monoids

[^2]: A more in depth introduction to Currying can be found at

http://learnyouahaskell.com/higher-order-functions#curried-functions

expand_less