Types
Featured image vector created by brgfx – www.freepik.com
Although functional programming can be done in a dynamically typed language (Lisp, the functional programming language forerunner, had no types), strong static type adds a very natural complement to functional programming.
From a mathematical point of view, a function sets a relationship between the set defined by the function argument (domain in math speaking) and the corresponding results (co-domain). Algebra studies exactly these relationships and may help the programmer in proving certain properties of the functions composing the programs.
Algebraic Data Types (ADT) are aggregated types in the algebra context. Two ADTs are of particular interest – sum types and product types. With sum and product referring to the resulting number of possible values (i.e. cardinality of sets).
Let’s say that an int has N possible different values, while a char has M different values. struct {int a; char b; } is a product type because it has MxN possible different values. While union { int a; char b; } is a sum type, because it has M+N possible different values.
C++ clearly has both sum and product types, even if built-in sum type (union) is generally discouraged in favor of the library alternative (std::variant). Product data types come into two flavors – built-in (struct and class) and library (std::tuple).
The most interesting group of ADT is the Sum Types to the point that I’ve seen several times considered synonyms in informal contexts.
Let’s consider the node of a binary tree. It can be either a leaf or an intermediate node. Leaves have an actual value, intermediate nodes have left and right children. If you, like me, come from an OOP background, you might be tempted to model this with an inheritance relationship:
class Node {};
class IntermediateNode : public Node
{
public:
Node* getRightChild();
Node* getLeftChild();
};
template<typename Value>
class Leaf : public Node
{
public:
Value getValue();
};
This may work, until this surfaces in the external interface. At that point, nothing is preventing an evil programmer to inherit from Node a inject its own EvilNode into your binary tree. Maybe everything sorts out fine, but maybe this messes things up because your implementation only expects two kinds of nodes.
Rust uses a brilliant solution for defining sum types, taking advantage of the close relationship between sum types and enums. After all, this type enumerates all its possible values.
enum Node<Value>
{
IntermediateNode(Box<Node<Value>>, Box<Node<Value>> ),
Leaf(Value)
}
(Box notation is needed to avoid defining an infinitely recursive type). In Scala you can do pretty much the same with sealed traits, resulting in something not so far away from C++:
sealed trait Node case class IntermediateNode( left: Node, right: Node) extends Node case class Leaf[A]( value: A ) extends Node
Being a sealed trait, no one, outside the package can inherit from the trait.
As you can see FP sum types tend to be quite empty, having just the more characteristic attribute(s), but no code. The reason is that the type just brings type value while the logic is in the code, completely decoupling data from code.
In Scala, the inheritance relationship is used just for defining the sum type, not for virtual methods. This kind of use of types brings the problem of downcast and type identification.
Although In OOP we know that trying to identify a type and downcasting a generic object to a specific one, is usually a sign of bad design. –
float f( Shape* shape )
{
Rectangle* rect = dynamic_cast<Rectangle*>(shape);+
if( rect != nullptr )
{
return rect->getSide(0)*rect->getSide(1);
}
// ....
}
In FP this is encouraged and supported via pattern matching:
def f( shape: Shape ) = {
shape match
{
case Rectangle(a,b) => a*b
...
}
}
The most important difference (set aside the elegance of pattern matching) is that being a sum type, the compiler knows all the alternatives and is able to check whether your match covers all the cases or not, and may give proper diagnostic.
Now, the bad design above is just bad design. The right OOP design is to have a virtual method that computes the area and to have it implemented inside every shape. But this and the pattern matching approaches are just two different ways of dealing with the same problem. Each one has advantages and disadvantages, but if the FP way of doing is to strip classes from code and move code into functions, then you need to follow this approach if you want to fully support the paradigm.
C++ does not support pattern matching although some attempts have been made (C++14 pattern matching, C++11 pattern matching by Stroustrup).
Going further there is another feature that is quite used in FP – the Higher Kinded Types (HKT). Trivially translated into C++ jargon, HKTs are templates of templates, i.e. a template whose parametric type is a template.
The idea is a generalization of the function. A function maps a value a to a value b, formally f: a -> b. A higher-order function takes a function as an argument: f: (a -> b) -> c (or takes a value and produces a function, but let’s stick with the former for sake of simplicity).
A generic/template function maps a type T, to another type U (e.g. a std::vector<> is a kind of functions that takes the type T and creates a new type that is std::vector<T>). A higher kinded type is a construct that takes a generic/template and maps it to another type.
Now, you may wonder what kind of application is for this abstraction in your code. Actually, there are a number of situations where HKTs are really useful to minimize code duplication. I have already talked about monads, as wrappers for types. Consider Options and Either, now what if you want to define a function on monads regardless they are Options or Eithers? It would be nice to express a template over a template, something like template<template<T>>…
To be honest, I thought that C++ couldn’t do something like this, but after a quick search on stackoverflow I had to retract. I just copy and paste below the solution by kennytm (I don’t claim any credit for):
template <template <typename> class m>
struct Monad {
template <typename a>
static m<a> mreturn(const a&);
template <typename a, typename b>
static m<b> mbind(const m<a>&, m<b>(*)(const a&));
};
Anyway, note that function pointers instead of generic function have been used, I guess for sake of simplicity.
In this post I’ve examined how C++ deals with type when compared with a functional programming language.
C++ offers strong typing and aside from the pattern matching tool, offers all the basic blocks needed to build function programming constructs. But, as already pointed out previously, C++ lacks of the friendliness in helping the programmer to actually write this code and to the reader to actually read effortlessly this code.