Learning #3: A First Attempt at a Haskell-ish Functor in C++

Over the past week or two, I have been reading about and listening to podcasts on Haskell, trying to gain a sense and understanding of Functors, Applicatives, and Monads. With a decent understanding of Functors, I attempted to implement similar functionality in C++. This is likely a work in progress (going to try to make it a little more semantically similar tomorrow), however it almost sort of kind of works.

Functors in Haskell

Functors allow you to apply some function over a parameterized type. By implementing a Functor for a given parameterized type, let’s call it a structure, you define how a function can be applied to the contents of the structure. Consider the Optional type – literally a copy of the Maybe type – which says either we have Something with a value inside or Nada which is nothing, void, null, etc. It is defined as follows:

data Optional a = Something a | Nada
  deriving (Show)

To define a functor for Optional we must define fmap:

instance Functor Optional where
  -- fmap (a -> b) -> Optional a -> Optional b
  fmap _ Nada = Nada
  fmap f (Something a) = Something (f a)

Thus, if we load this into the GHCI REPL, we can do the following:

fmap (+1) Something 10 -- Something 11
fmap (+1) Nada         -- Nada

A Functor in C++ Attempt #1

Clearly C++ is missing a few of these nice functional features necessary to simply implement a functor, namely sum types and class types. However, we can get sort of close.

First, I tried to define the Optional Type. It seemed trivial to construct a tagged union inside a template to create a sort of parameterized type.

template<typename a>
union Optional {
  a something;

Howevever this will not work because I have no way to define Nada and no way for the Optional to know which variant is used. Thus, I stuck my union inside a class which encapsulates a variant int that keeps track fo which variant is used. I then overloaded the constructor, creating one instance for Something and another for Nada.

template<typename a, typename b>
class OptionalWrapper {
    int variant;
    Optional<a> o;

    OptionalWrapper() { variant = 1; }
    OptionalWrapper(a val) { o = {val}; variant = 0; }

With this OptionalWrapper I then am able to define a fmap function which takes a function, applies it to the contents of the OptionalWrapper and in a pure manner, returns a new OptionalWrapper

 OptionalWrapper<a,b>* fmap(std::function<b(a)> f) { 
      switch (variant) {
        case 0: {
          auto new_o = f(o.something); 
          return new OptionalWrapper(new_o);
        case 1:
          return new OptionalWrapper();

Thus, I can now mimick some of the above Haskell functor functionality:

auto owa = new OptionalWrapper<int, int>(10);
owa->print(); // Something (10)
auto owb = owa->fmap([](int a) -> int { return a + 1; });
owb->print(); // Something (11)

auto owc = new OptionalWrapper<int, int>();
owc->print(); // Nada
auto owd = owc->fmap([](int a) -> int { return a + 1; });
owd->print(); // Nada

This has some rather obvious inelegancies that are due to implementation details, not language deficiences:

I am probably going to work on fixing some of these up tomorrow.