Type Constructor Polymorphism: Implementation Specs

Category.hx

interface Category<M> 
{
  // identity value in this category
  public function id <A>():OfOf<M, A, A>;
  /**
   * Category composition Operator.
   * 
  **/
  public function dot <A,B,C>(g:OfOf<M, B, C>, f:OfOf<M, A, B>):OfOf<M, A, C>;

}

// A->A is equivalent to OfOf<In->In, A->A> because In->In is a type constructor (could also be written as (->)<A,A>)

class FunctionCategory implements Category<In->In> 
{
  
  
  // identity function
  public function id <A>():A->A 
  {
     return function (x) return x;
  }
  
  // Function composition
  public function dot <A,B,C>(g:B->C, f:A->B):A->C 
  {
     return function (x) return g(f(x));
  } 

}

class CategorySyntax {
    public static function id <M,A>(c:Category<M>):OfOf<M, A, A> {
       return c.id();
    }
  /**
   * Category composition Operator.
   * 
  **/
  public static function dot <M,A,B,C>(g:OfOf<M, B, C>, f:OfOf<M, A, B>, c:Category<M>):OfOf<M, A, C> 
  {
     return c.dot(g,f);
  }
}

using CategorySyntax;

class Main {
  public static function main () {
    var cat = new FunctionCategory();
    var f = (function (x) return "result: " + Std.string(x)).dot(function (x) return x+2, cat); // Int->String
    trace(f(4)); // "result: " + 6
  }

}

Main.hx

// Of represents a Type Constructor
abstract Of<M,A>(Dynamic) {} // alternative name MA


// OfOf represents a Type constructor function that takes two types. 

abstract OfOf<M,A,B>(Dynamic) {} // alternative name MAB

// alternative OfOf implementation, maybe easier to implement

typedef OfOf<M,A,B> = Of<Of<M, A>, B>;

// In is used to represent a specific but not applied type constructor, e.g. Array => Array<In>
abstract In(Dynamic) {}

interface Monad<M> {
    public function fmap<A,B>(x:Of<M,A>, f:A->B):Of<M,B>;
    public function flatMap<A,B>(x:Of<M,A>, f:A->Of<M,B>):Of<M,B>;
    public function pure<A>(x:A):Of<M,A>;
}

// Some monads

class ArrayMonad implements Monad<Array<In>> 
{
    public function new () {}
    public function fmap<A,B>(x:Array<A>, f:A->B):Array<B> {
       return x.map(f);
    }

    public function flatMap<A,B>(x:Array<A>, f:A->Array<B>):Array<B> {
       var r = [];
       for (e in x) {
          for (e1 in f(e)) {
             r.push(e1);
          }
       }
       return r;
    }

    public function pure<A>(x:A):Array<A> {
       return [x];
    }
}

class EitherMonad<L> implements Monad<Either<L, In>> 
{
    public function new () {}
    public function fmap<A,B>(x:Either<L, A>, f:A->B):Either<L, B> {
        return switch (x) {
           case Right(r): Right(f(r));
           case Left(l): Left(l);
        }
    }

    public function flatMap<A,B>(x:Either<L, A>, f:A->Either<L, B>):Either<L, B> {
        return switch (x) {
           case Right(r): f(r);
           case Left(l): Left(l);
        }
    }

    public function pure<A>(x:A):Either<L, A> {
       return Right(x);
    }
}


class MonadSyntax {
    public static function fmap<M,A,B>(x:Of<M,A>, f:A->B, m:Monad<M>):Of<M,B> 
    {
       return m.fmap(x,f);
    }
    public static function flatMap<M,A,B>(x:Of<M,A>, f:A->Of<M,B>, m:Monad<M>):Of<M,B>
    {
       return m.flatMap(x, f);
    }
    public static function pure<M, A>(x:A, m:Monad<M>):Of<M,A> {
      return m.pure(x);
    }
}

// explicit usage (implicit usage can be achieved by macros)

using MonadSyntax;

class Main {
   public static function main () {
     
     // Array usage
     var monad = new ArrayMonad();
     // Array<Int> is equivalent to Of<Array<In>, Int>.
     // f (Int->Array<Int>) is compatible to Int->Of<Array<In>, Int>
     [1].flatMap(function (x) return [x, x+1], monad); // [1,2] 
     [1].fmap(function (x) return x + 1, monad); // [2]
     1.pure(monad); // [1]

     // Either usage
     
     var monad = new EitherMonad();

     // If a type has more than one type parameters like Either it unifies with Of<Either<L, In> R> 
     // (because type parameters are applied from Right to Left).
     Right(1).fmap(function (x) return x+1, monad); // Right(2)


   }
}

UnificationRules.md

Unification Rules - type parameters are applied from right to left by default (good idea?)

Expected -- Current => Unification

• Of<M, T> -- Array<T> => passes: M = Array<In> && T = T
• Array<A> -- Of<Array<In>, T> => passes: A = T
• Array<String> -- Of<Array<In>, Int> => fails: Int should be String
• Either<A,B> -- Of<Either<L, In>, R> => passes: A = L && B = R
• Either<A,B> -- Of<Of<Either<In, In>, L>, R> => passes A = L && B = R
• Of<M,T> -- Either<L,R> => passes: M = Either<L, In> && T = R
• Of<Of<M,A>,B> -- Either<L,R> => passes: M = Either<In, In> && A = L && B = R
• Of<Of<M,A>,B> -- Array<R> => fails: Array<R> should be OfOf<M,A,B>
• Of<M,T> -- P1->P2 => passes: M = P1->In && T = P2
• Of<M, Option<>T> -- Array<Option<S>> => passes: M=Array<In> && T = S
• Array<Option<T>> -- Of<Array<In>, Option<S>> => passes: T = S
• Of<Of<M,A>,B> -- P1->P2 -- passes: M = In->In && A = P1 && B = P2>
• Of<Of<M, A>, B> -- Array<Option<T>> => passes: M = Array<In> && A = Option<In> && = B = T
• Array<Option<T>> -- Of<Of<Array<In>, Option<In>>, B> => passes: T = B

Left to Right substitution could be achieved with a reversed abstract:

abstract LeftProjection<R,L>(Either<L,R>) {}

here is another example use case: https://gist.github.com/frabbit/87f69012620499a747c9

and another one: https://gist.github.com/frabbit/7979748