Functor, Maybe, and Higher-Kinded Types in C++

hkt.cpp

// Example program
#include <iostream>
#include <string>
#include <vector>
#include <type_traits>
 
//---------------------
// Maybe and MyVector, two totally unrelated classes whose only commanilty is that they are both type constructors of the same arity (e.g. 1) and order (e.g. 1).
//---------------------
template< typename T >
struct Maybe
{
    Maybe(T const& v) : value(v), nothing(false) {}
    Maybe() : nothing(true) {}
    std::string desc() const
    {
        if (nothing) return "Nothing";
        else return "Some(" + std::to_string(value) + ")";
    }
    
    T value;
    bool nothing;
};

template< typename T >
struct MyVector
{
  std::vector< T > vec;
};

//---------------------
// A functor is a typeclass for the map function.
// All instances (e.g. specializations) should implement the fmap function:
//    template< typename B, typename A, typename TFunction >
//    static F< B > fmap(F< A > const& x, TFunction func);
// Usually a typeclass will require that you implement more than just one function
// which is when it becomes beneficial to group the functions into a class for the
// purposes of namespacing and enforcing that all functions are implemented.
// However, if the typeclass is only one function, then it may be simpler
// to use plain function overloading and avoid template template parameters and specializations.
// Both methods are implemented here for illustration. 
//---------------------/
template< template< typename > class F >
struct Functor;

//---------------------
// Instances of the functor typeclass for Maybe and MyVector
//---------------------
template < >
struct Functor< Maybe >
{
  template< typename A, typename TF >
  static Maybe< typename std::result_of< TF(A) >::type >
  fmap(Maybe< A > const& x, TF func)
  {
    using Result = typename std::result_of< TF(A) >::type;
    if (x.nothing) return Maybe< Result >();
    else return Maybe< Result >(func(x.value));
  }
};

template < >
struct Functor< MyVector >
{
  template< typename A, typename TF >
  static MyVector< typename std::result_of< TF(A) >::type >
  fmap(MyVector< A > const& x, TF func)
  {
    using Result = typename std::result_of< TF(A) >::type;
    MyVector< Result > result;
    for (A const& v : x.vec)
    {
        result.vec.push_back(func(v));
    }
    return result;
  }
};

// The function overloading alternative

template< typename A, typename TF >
Maybe< typename std::result_of< TF(A )>::type >
fmap(Maybe< A > const& x, TF func)
{
  using Result = typename std::result_of< TF(A) >::type;
  if (x.nothing) return Maybe< Result >();
  else return Maybe< Result >(func(x.value));
}

template< typename A, typename TF >
MyVector< typename std::result_of< TF(A) >::type >
fmap(MyVector< A > const& x, TF func)
{
  using Result = typename std::result_of< TF(A) >::type;
  MyVector< Result > result;
  for (A const& v : x.vec)
  {
      result.vec.push_back(func(v));
  }
  return result;
}

//---------------------
// A random function that operates on strings that we'd like to apply to any type T<std::string> without writing any glue code.
//---------------------
size_t length(std::string const& str)
{
  return str.size();
}

//---------------------
// A class that has the same order and arity as Maybe and MyVector, but for which we purposefully don't define a functor isntance.
//---------------------
template< typename T >
struct HasNoFunctorInstance
{
  T value;
};


int main()
{
  Maybe<std::string> opt1("Hello, world!");
  Maybe<std::string> opt2;
  MyVector<std::string> vec = { .vec = {"One", "Two", "Three"} };
  HasNoFunctorInstance<std::string> bad;
  
  
  // So what's the point? Well now, given any function that operates on strings
  // we can apply it to any type of the form T<std::string> given that a functor
  // instance (aka functor specialization) is available for that type. Without
  // Higher-Kinded Types, we would have to write custom glue code for every
  // combination of function and type T<std::string>.
  
  auto opt1Len = fmap(opt1, length);
  // or using the Functor class.
  auto opt2Len = Functor<Maybe>::fmap(opt2, length);
  // we can even apply length to other types.
  MyVector<size_t> vecLen = fmap(vec, length);
  // 
  //auto bad2 = fmap(bad, length); // error: no matching function for call to 'fmap'
  //auto bad3 = Functor<HasNoFunctorInstance>::fmap(bad, length); // error: implicit instantiation of undefined template 'Functor<HasNoFunctorInstance>'
  
  // print the results
  std::cout << opt1Len.desc() << std::endl;
  std::cout << opt2Len.desc() << std::endl;
  for (auto&& i : vecLen.vec)
  {
    std::cout << i << " ";
  } 
  std::cout << std::endl;
  
  return 0;
}