Example of the use of category theory in functional programming Modern functional programming introduces a few new ideas. For instance, the program is understood as a mathematical formula rather than a list of instructions. When this idea is implemented in a programming language, the process of running the program takes on features analogous to mathematical calculation or a logical proof, which allows us to use the rich mathematical intuition accumulated over centuries of development of mathematics.
Another key idea is to introduce higher-rank types. A 0-rank type is an ordinary type that can have values; for example, "integer" or "a pair of two booleans" or "an array of strings". Consider now the type of "array of strings"; this type can be generalized to "an array of X" where X is any 0-rank type. Then "array" itself is a rank-1 type, that is, a type parameterized by a 0-rank type. Another way of looking at a rank-1 type is to interpret this as a function from 0-rank type to 0-rank type. Note that we cannot have values of type "array", we can only have values of a 0-rank type. We can have values of type "array of string".
In this way, we can define rank-1 types, rank-2 types, etc. - but it is not immediately clear what we should do with them. Category theory provides guidance about what to do with higher-rank types and how to use them for programming. The "array" type provides a simple example of how category theory helps programming.
The "array" type is a rank-1 type, that is, a "type mapping". The correspondence between functional programming and category theory is based on considering the category whose objects are the data types available in our programming language. So, a rank-1 type corresponds to a mapping from objects to objects in that category. However, category theory normally considers functors rather than just bare type mappings, because functors are more useful. In the language of types, a functor is a rank-1 type F with an additional "fmap" method that lifts any function f : a -> b into a function F a -> F b.
Using "array" as "F", we find that "array" would be a functor if we could define "fmap" such that any f: (a->b) is transformed into a function of type array(a) -> array(b). We can certainly define this "fmap" by applying "f" to every element of the array; the result will be an array of values of type "b", as required. So "array" is indeed a functor.
Now, notice that the code
fmap f arr is equivalent to a loop over the array
arr. If "fmap" is in the standard library of our programming language, we can apply transformations to arrays without ever writing any loops! This is a significant benefit for programmers, because loops are a common source of errors.
Category theory in fact suggests a few more operations that the "array" type should have ("fold", "scan", "flatten", etc.). With these operations, pretty much any array manipulation becomes just an application of some standard library functions, without a single loop ever to be written.
Modern functional languages (such as Haskell and Scala) include a rich library of such functions. These functions are, in many cases, a straightforward translation of a construction from category theory into the programming language. The result is a versatile collection of algorithm-agnostic data and control structures that can be used to simplify coding in a wide variety of situations. It is remarkable that many constructions in category theory (such as functors, natural transformations, or monads) turned out to be useful for practical programming, even though these constructions were invented by mathematicians for very different purposes.