DEV Community

Muhammad Ahmad
Muhammad Ahmad

Posted on

Functional Programming in JS: 0x06 - Category Theory - Theme 1

Category theory

Category theory is the theoretical concept that empowers function composition. Category theory and function composition go together like engine displacement and horsepower, like NASA and the space shuttle, like good beer and a mug to pour it in. Basically, you can’t have one without the other.

Category theory in a nutshell

Category theory really isn’t too difficult a concept. Its place in math is large enough to fill up an entire graduate-level college course, but its place in computer programming can be
summed up quite easily.

Einstein once said, “If you can’t explain it to a 6-year-old, you don’t know it yourself”. Thus, in the spirit of explaining it to a 6-year-old, category theory is just connecting the dots. Although it may be grossly over-simplifying category theory, it does do a good job of explaining what we need to know in a straightforward manner.

First you’ll need to know some terminology. Categories are just sets with the same type.

In JavaScript, they’re arrays or objects that contain variables that are explicitly declared as numbers, strings, Booleans, dates, nodes, and so on. Morphisms are pure functions that, when given a specific set of inputs, always return the same output. Homomorphic operations are restricted to a single category, while polymorphic operations can operate on multiple categories. For example, the homomorphic function multiplication only works on numbers, but the polymorphic function addition can work on strings too.

category 1

The following diagram shows three categories—A, B, and C—and two morphisms—ƒ and ɡ.
Category theory tells us that, when we have two morphisms where the category of the first one is the expected input of the other, then they can be composed to the following:

category 2

The ƒ o g symbol is the composition of morphisms ƒ and g. Now we can just connect the dots.

category 3

Type safety

Let’s connect some dots. Categories contain two things:

  1. Objects (in JavaScript, types).
  2. Morphisms (in JavaScript, pure functions that only work on types).

These are the terms given to category theory by mathematicians, so there is some unfortunate nomenclature overloading with our JavaScript terminology. Objects in category theory are more like variables with an explicit data type and not collections of properties and values like in the JavaScript definition of objects. Morphisms are just pure functions that use those types.

So applying the idea of category theory to JavaScript is pretty easy. Using category theory in JavaScript means working with one certain data type per category. Data types are numbers, strings, arrays, dates, objects, Booleans, and so on. But, with no strict type system in JavaScript, things can go awry. So we’ll have to implement our own method of ensuring that the data is correct.

There are four primitive data types in JavaScript: numbers, strings, Booleans, and functions. We can create type safety functions that either return the variable or throw an error. This fulfils the object axiom of categories.

var str = function(s) {
    if (typeof s === "string") {
        return s;
    } else {
        throw new TypeError("Error: String expected, " + typeof s + " given.");
    }
}
var num = function(n) {
    if (typeof n === "number") {
        return n;
    } else {
        throw new TypeError("Error: Number expected, " + typeof n + " given.");
    }
}
var bool = function(b) {
        if (typeof b === "boolean") {
            return b;
        } else {
            throw new TypeError("Error: Boolean expected, " + typeof b + "
                given.
                ");
            }
        }
        var func = function(f) {
                if (typeof f === "function") {
                    return f;
                } else {
                    throw new TypeError("Error: Function expected, " + typeof f + "
                        given.
                        ");
               }
          }
Enter fullscreen mode Exit fullscreen mode

However, there’s a lot of repeated code here and that isn’t very functional. Instead, we can create a function that returns another function that is the type safety function.

var typeOf = function(type) {
    return function(x) {
        if (typeof x === type) {
            return x;
        } else {
            throw new TypeError("Error: " + type + " expected, " + typeof x + " given.");
        }
    }
}
var str = typeOf('string'),
    num = typeOf('number'),
    func = typeOf('function'),
    bool = typeOf('boolean');
Enter fullscreen mode Exit fullscreen mode

Now, we can use them to ensure that our functions behave as expected.

// unprotected method:
var x = '24';
x + 1; // will return '241', not 25
// protected method
// plusplus :: Int -> Int
function plusplus(n) {
    return num(n) + 1;
}
plusplus(x); // throws error, preferred over unexpected output
Enter fullscreen mode Exit fullscreen mode

Let’s look at a meatier example. If we want to check the length of a Unix timestamp that is returned by the JavaScript function Date.parse(), not as a string but as a number, then we’ll have to use our str() function.

// timestampLength :: String -> Int
function timestampLength(t) {
    return num(str(t).length);
}
timestampLength(Date.parse('12/31/1999')); // throws error
timestampLength(Date.parse('12/31/1999')
    .toString()); // returns 12
Enter fullscreen mode Exit fullscreen mode

Functions like this that explicitly transform one type to another (or to the same type) are called morphisms. This fulfils the morphism axiom of category theory. These forced type declarations via the type safety functions and the morphisms that use them are everything we need to represent the notion of a category in JavaScript.

Object identities

There’s one other important data type: objects.

var obj = typeOf('object');
obj(123); // throws error
obj({
    x: 'a'
}); // returns {x:'a'}`
Enter fullscreen mode Exit fullscreen mode

However, objects are different. They can be inherited. Everything that is not a primitive— numbers, strings, Booleans, and function—is an object, including arrays, dates, elements, and more.

There’s no way to know what type of object something is, as in to know what sub-type a JavaScript ‘object’ is, from the typeof keyword, so we’ll have to improvise. Objects have a toString() function that we can hijack for this purpose.

var obj = function(o) {
    if (Object.prototype.toString.call(o) === "[object Object]") {
        return o;
    } else {
        throw new TypeError("Error: Object expected, something else given.");
    }
}
Enter fullscreen mode Exit fullscreen mode

Again, with all the objects out there, we should implement some code re - use.

var objectTypeOf = function(name) {
        return function(o) {
            if (Object.prototype.toString.call(o) === "[object " + name + "]") {
                return o;
            } else {
                throw new TypeError("Error: '+name+' expected, something else
                    given.
                    ");
                }
            }
        }
        var obj = objectTypeOf('Object');
        var arr = objectTypeOf('Array');
        var date = objectTypeOf('Date');
        var div = objectTypeOf('HTMLDivElement');
Enter fullscreen mode Exit fullscreen mode

These will be very useful for our next topic: functors.

Functors

While morphisms are mappings between types, functors are mappings between categories.

They can be thought of as functions that lift values out of a container, morph them, and then put them into a new container. The first input is a morphism for the type and the second input is the container.

Note

The type signature for functors looks like this:
// myFunctor :: (a -> b) -> f a -> f b
This says, “give me a function that takes a and returns b and a box that contains a(s), and I’ll return a box that contains b(s).

Creating functors

It turns out we already have one functor: map(). It grabs the values within the container, an array, and applies a function to it.

[1, 4, 9].map(Math.sqrt); // Returns: [1, 2, 3]
Enter fullscreen mode Exit fullscreen mode

However, we’ll need to write it as a global function and not as a method of the array object. This will allow us to write cleaner, safer code later on.

// map :: (a -> b) -> [a] -> [b]
var map = function(f, a) {
    return arr(a).map(func(f));
}
Enter fullscreen mode Exit fullscreen mode

This example seems like a contrived wrapper because we’re just piggybacking onto the map() function. But it serves a purpose. It provides a template for maps of other types.

// strmap :: (str -> str) -> str -> str
var strmap = function(f, s) {
    return str(s).split('').map(func(f)).join('');
}
// MyObject#map :: (myValue -> a) -> a
MyObject.prototype.map(f {
            return func(f)(this.myValue);
        }
Enter fullscreen mode Exit fullscreen mode

Arrays and functors

Arrays are the preferred way to work with data in functional JavaScript.

Is there an easier way to create functors that are already assigned to a morphism? Yes, and it’s called arrayOf.

When you pass in a morphism that expects an integer and returns an array, you get back a morphism that expects an array of integers and returns an array of arrays.
It is not a functor itself, but it allows us to create functors from morphisms.

// arrayOf :: (a -> b) -> ([a] -> [b])
var arrayOf = function(f) {
    return function(a) {
        return map(func(f), arr(a));
    }
}
Enter fullscreen mode Exit fullscreen mode

Here’s how to create functors by using morphism:

var plusplusall = arrayOf(plusplus); // plusplus is our morphism
console.log( plusplusall([1,2,3]) ); // returns [2,3,4]
console.log( plusplusall([1,'2',3]) ); // error is thrown
Enter fullscreen mode Exit fullscreen mode

The interesting property of the arrayOf functor is that it works on type safeties as well.

When you pass in the type safety function for strings, you get back a type safety function for an array of strings. The type safeties are treated like the identity function morphism.

This can be very useful for ensuring that an array contains all the correct types.

var strs = arrayOf(str);
console.log( strs(['a','b','c']) ); // returns ['a','b','c']
console.log( strs(['a',2,'c']) ); // throws error
Enter fullscreen mode Exit fullscreen mode

Function compositions, revisited

Functions are another type of primitive that we can create a functor for. And that functor is called fcompose. We defined functors as something that takes a value from a container and applies a function to it.

When that container is a function, we just call it to get its inner value. We already know what function compositions are, but let’s look at what they can do in a category theory-driven environment.

Function compositions are associative. If your high school algebra teacher was like mine, she taught you what the property is but not what it can do. In practice, compose is what the associative property can do.

(a×b)×c=a×(b×c) (a \times b) \times c = a \times (b \times c)
(ab)c=a(bc) (a \cdot b) \cdot c = a \cdot (b \cdot c)
fggf f \cdot g \neq g \cdot f

We can do any inner-compose, it doesn’t matter how it’s grouped.

This is not to be confused with the commutative property. ƒ o g does not always equal g o ƒ. In other words, the reverse of the first word of a string is not the same as the first word of the reverse of a string.

What this all means is that it doesn’t matter which functions are applied and in what order, as long as the input of each functions comes from the output of the previous function.

But wait, if the function on the right relies on the function on the left, then can’t there be only one order of evaluation? Left to right? True, but if it’s encapsulated, then we can control it however we feel fit. This is what empowered lazy evaluation in JavaScript.

(a×b)×c=a×(b×c) (a \times b) \times c = a \times (b \times c)
(ƒg)h=ƒ(gh) (ƒ \cdot g) \cdot h = ƒ \cdot (g \cdot h)

Let’s rewrite function composition, not as an extension of the function prototype, but as a stand-alone function that will allow us to get more out of it. The basic form is as follows:

var fcompose = function(f, g) {
    return function() {
        return f.call(this, g.apply(this, arguments));
    };
};
But we ll need it to work on any number of inputs.
var fcompose = function() {
    // first make sure all arguments are functions
    var funcs = arrayOf(func)(arguments);
    // return a function that applies all the functions
    return function() {
        var argsOfFuncs = arguments;
        for (var i = funcs.length; i > 0; i -= 1) {
            argsOfFuncs = [funcs[i].apply(this, args)];
        }
        return args[0];
    };
};
// example:
var f = fcompose(negate, square, mult2, add1);
f(2); // Returns: -36
Enter fullscreen mode Exit fullscreen mode

Now that we’ve encapsulated the functions, we have control over them. We could rewrite the compose function such that each function accepts another function as input, stores it, and gives back an object that does the same. Instead of accepting an array as an input, doing something with it, and then giving back a new array for each operation, we can accept a single array for each element in the source, perform all operations combined (every map(), filter(), and so on, composed together), and finally store the results in a new array.

This is lazy evaluation via function composition. No reason to reinvent the wheel here. Many libraries have a nice implementation of this concept, including the Lazy.js, Bacon.js and wu.js libraries.

There’s a lot more we can do as a result of this different model: asynchronous iteration,
asynchronous event handling, lazy evaluation, and even automatic parallelization.

Note

Automatic parallelization? There’s a word for that in the computer science industry: IMPOSSIBLE. But is it really impossible? The next evolutionary leap in Moore’s law might be a compiler that parallelizes our code for us, and could function composition be it?

No, it doesn’t quite work that way. The JavaScript engine is what is really doing the parallelization, not automatically but with well thought-out code. Compose just gives the engine the chance to split it into parallel processes. But that in itself is pretty cool.

If you like my content consider leaving a reaction, share to someone know may be interested in the topic or follow me on twiiter , thanks for reading :)

Discussion (0)