The Type Class Idiom in Haskell, Scala, C++, and Objective-C

.gitignore

*.class
*.swp

TypeClassExample.cpp

#include <iostream>
#include <sstream>
#include <tr1/functional>
#include <vector>
#include <numeric>
#include <sstream>
#include "Vector.h"

template <template <class> class C, class I>
struct instance;

#define RegisterInstance(Class,Param,Name)\
  struct instance<Class,Param> {\
    typedef Name T;\
  }

#define TCI(Class, Param) instance<Class,Param>::T
#define TTCI(Class, Param) typename instance<Class,Param>::T


template <class A>
struct TypeClass
{
  TypeClass(A v) : val (v) {}
  operator A() { return this->val; }
protected:
  A val;
};

template <class A>
struct Monoid : TypeClass<A>
{ 
  Monoid(A v) : TypeClass<A>(v) { }
  A plus(A);
  static A zero();
};

template <class C>
struct FoldLeft : TypeClass<C>
{
  FoldLeft<C>(C v) : TypeClass<C>(v) { }
  template <class A, class B>
  B foldLeft(B zero, std::tr1::function<B(B,A)> folder);
};


struct CharsMonoid : public Monoid<const char*>
{
  CharsMonoid(const char* str) : Monoid<const char* >(str) { };
  const char* plus(const char* str)
  {
    std::stringstream stream;
    stream << this->val << str;
    return stream.str().c_str();
  }
  
  static const char* zero()
  {
    return "";
  }
};

template <class A>
struct VectorFoldLeft : public FoldLeft<Vector<A> >
{
  VectorFoldLeft(Vector<A> vec) : FoldLeft<Vector<A> >(vec) { };
  template <typename B>
  B foldLeft(B zero, std::tr1::function<B(B,A)> folder)
  {
    std::vector<A> vec = this->val;
    return std::accumulate(vec.begin(), vec.end(), zero, folder);
  }
};

template <>
RegisterInstance(Monoid, const char*, CharsMonoid);

template <class A>
RegisterInstance(FoldLeft, Vector<A>, VectorFoldLeft<A>);


template <class A, template <class> class C>
A sum(TTCI(FoldLeft,C<TTCI(Monoid,A)>) foldable)
{
  struct {
    A operator()(A memo, A val)
    {
      return TTCI(Monoid,A)(memo).plus(val);
    }
  } append;
  
  return foldable.template foldLeft<A>(TCI(Monoid,A)::zero(), append);
}


int main(int argc, const char* argv[])
{
  typedef TCI(Monoid,const char*) ElemType;
  ElemType arr[] = { "a", "b", "c" };
  Vector<ElemType> vector(arr);
  
  std::cout << sum<const char*,Vector>(vector) << std::endl;
  return 0;
}

TypeClassExample.hs

{-# LANGUAGE TypeSynonymInstances #-}

module Main where
import Prelude hiding (sum)

class FoldLeft t where
  foldLeft :: (a -> b -> a) -> a -> t b -> a

class Monoid a where
  plus :: a -> a -> a
  zero :: a

instance Monoid String where
  plus = (++)
  zero = ""

instance FoldLeft [] where
  foldLeft = foldl

sum :: (Monoid m, FoldLeft t) => t m -> m -- this type annotation isn't even necessary
sum = foldLeft plus zero

main = (putStrLn . sum) ["a","b","c"]

TypeClassExample.m

typedef id (^FoldArrow)(id, id);

@protocol FoldLeft
- (id)foldLeftOnto:(id)object with:(FoldArrow)folder;
@end

@protocol Monoid
- (id<Monoid>)plus:(id<Monoid>)val;
+ (id<Monoid>)zero;
@end

@interface NSArray (FoldLeft) <FoldLeft>
@end

@interface NSString (Monoid) <Monoid>
@end


@implementation NSString (Monoid)
- (id<Monoid>)plus:(id<Monoid>)val { return [self stringByAppendingString:val]; }
+ (id<Monoid>)zero { return @""; }
@end


@implementation NSArray (FoldLeft)
// I'll leave this implementation up to the reader
@end


id<Monoid> sum(id<Foldable> xs) {
  Class monoid = [[xs objectAtIndex:0] class];
  return [xs foldLeftOnto:[monoid zero] with:^(id m, id v) {
    return [m plus:v];
  }];
}

int main(int argc, char *argv[]) {
  NSLog(@"%@", sum([NSArray arrayWithObjects:@"a",@"b",@"c",nil]));
}

TypeClassExample.scala

trait FoldLeft[F[_]] {
  def foldLeft[A,B](t: F[A], z: B, f: (B,A) => B): B
}

trait Monoid[A] {
  def plus(a1: A, a2: A): A
  def zero: A
}

object Monoid {
  implicit val StringMonoid: Monoid[String] = new Monoid[String] {
    def zero: String = ""
    def plus(a1: String, a2: String): String = a1 + a2
  }
}

object FoldLeft {
  implicit val ListFoldLeft: FoldLeft[List] = new FoldLeft[List] {
    def foldLeft[A,B](t: List[A], z: B, f: (B,A) => B): B =
      t.foldLeft(z)(f)
  }
}

object TypeClassExample {
  def sum[C[_],T](xs: C[T])(implicit m: Monoid[T], f: FoldLeft[C]): T = 
    f.foldLeft(xs, m.zero, m.plus)

  def main(args: Array[String]) : Unit = println(sum(List("a","b","c")));
}