Haskell in C++: Implementing pure functional constructs in c++ using templates

When I first learnt Haskell a while back, I found it difficult to adjust my thinking to the pure-functional style. Especially because I have been coding in imperative languages for more than 7 years before that. It took me a while to fully grasp and appreciate the elegance of these constructs in Haskell, like functors and monads. At some point, I attempted to implement the same constructs in C++, to help my understanding, and get a feel of the expressive power Haskell has.

§ Prerequisites

I am assuming basic knowledge of both c++ (with templates) and Haskell. I will be using clang++ 11.0.0; c++17 and ghc 8.10.4, but I believe most of these should work on any compiler/version.

§ First blood: Basic Types

Before we dive deep, it is good to rewrite some simple concepts - such as standard types - to ensure we are on the right track.

-- haskell
type Int
type Char
type Float

// c++
using Int = int;
using Char = char;
using Float = float;

I wrapped the c++ primitive types for naming consistency.

Parametrized Types

Now we implement the primitive Maybe type. STL already has a type that fits the exact requirement: std::optional (c++17 onwards), so we will just use that.

type Maybe a
  = Nothing
  | Just a

#define Maybe std::optional

template<typename A>
Maybe<A> Nothing() { return Maybe<A>(); }

template<typename A>
Maybe<A> Just(A a) { return Maybe<A>(a); }

For ease of implementation, all objects are passed by value by making copies. This is inefficient, but captures the semantics correctly.

x :: Maybe Int
x = Just 4

Maybe<Int>
x = Just(4);

§ The Functor Typeclass

Haskell supports polymorphism using typeclasses. A typeclass specifies an interface that the type should implement. In this blog, I will demonstrate how to implement the simple functor typeclass. Note: The implementation is hacky, with the goal of making this simple and easy to understand. I will write a more generic version of this in a future continuation blog post.¹

class Functor f where
  fmap :: (a -> b) -> f a -> f b

instance Functor Maybe where
  fmap f Nothing = Nothing
  fmap f (Just x) = Just (f x)

template <typename A, typename B>
Maybe<B> fmap(std::function<B(A)> fn, Maybe<A> ma) {
  if (!ma.has_value())
    return Nothing<B>();
  else
    return Just(fn(ma.value()));
}

§ Basic Usage

Well, that is it! Now time to test it out.

-- import Data.Char(chr)

a, b :: Maybe Int
a = Just 97
b = Nothing

aa, bb :: Maybe Char
aa = fmap chr a -- Just 'a'
bb = fmap chr b -- Nothing

Maybe<Int> a = Just(4);
Maybe<Int> b = Nothing<Int>(); // c++ is not too great at type deduction

std::function<Char(Int)>
  chr = [](int x) { return (char)x; };

Maybe<Char> aa = fmap<int, char>(chr, a);
Maybe<Char> bb = fmap<int, char>(chr, b);

§ More complex types: Lists

A natural extension of Maybe is List. And it is a very common primitive in almost every language.

type List a
  = Nil
  | Cons a (List a)

#define List std::stack

template <typename A>
List<A> Nil() { return {}; }

template <typename A>
List<A> Cons(A a, List<A> as) {
  as.push(a);
  return as;
}

This is surely a shortcut and not an exact implementation. But the idea is to roughly capture the same concepts in c++, for which this works fine.

Now to define the Functor instance of List, which is very similar to before - overload the fmap function.

instance Functor List where
  fmap f Nil = Nil
  fmap f (Cons a as) = Cons (f a) (fmap f as)

template <typename A, typename B>
List<B> fmap(std::function<B(A)> fn, List<A> as) {
  if (as.empty()) {
    return Nil<B>();
  } else {
    A head = as.top();
    as.pop();
    return Cons(fn(head), fmap(fn, as));
  }
}

And finally a few examples to make the usage and semantics clear:

emp, xs :: List Int
emp = Nil
xs = Cons 1 (Cons 2 (Cons 3 emp))

add5 :: Int -> Int
add5 x = x + 5

ys :: List Int
ys = fmap add5 xs -- [6, 7, 8]

List<Int> emp = Nil<Int>();
List<Int> xs = Cons(1, Cons(2, Cons(3, emp)));

std::function<Int(Int)>
  add5 = [](Int x) { return x + 5; };


List<Int> ys = fmap(add5, xs);

§ Conclusions

I demonstrate how to implement some very basic Haskell constructs in c++ (with some hacks to make things simpler). Hopefully, this gives a better understanding of these functional constructs to an imperative programmer.
In the next blog on this series, I will explore how to build the IO monad using similar primitives. That is usually one of the most confusing concepts for beginner haskellers, and hopefully this exposition will aid their learning.

§ Food for Thought

There are a few natural extensions to the above experiment, that one could try:

Implement sum types (with tags) and case.
Implement the IO monad.
Laziness/Thunking: Starting with lazy lists, maybe make the Fibonacci example work.

I skip the (<$) operator as it provides no additional insight. But it should be fairly trivial to extend and implement it. ↩

Last updated: 22.05.2021