Implement Haskell typeclass with C# interface

Question

I'm trying to compare Haskell's type classes and C#'s interfaces. Suppose there is a Functor.

Haskell:

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

How to implement this type class as interface in C#?

What I have tried:

interface Functor<A, B>
{
    F<B> fmap(Func<A, B> f, F<A> x);
}

This is invalid implementation and I'm actually stucked with generic F type that should be returned by fmap. How it should be defined and where?

Is it impossible to implement Functor in C# and why? Or maybe there is another approach?

Answer 1

C#'s type system lacks a couple features necessary to properly implement type classes as an interface.

Let's start with your example, but the key is showing a fuller account of what a typeclass is and does, and then trying to map those to C# bits.

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

This is the type class definition, or similar to the interface. Now let's look at a definition of a type and it's implementation of that type class.

data Awesome a = Awesome a a

instance Functor Awesome where
  fmap f (Awesome a1 a2) = Awesome (f a1) (f a2)

Now we can see very obviously one distinct fact of type classes that you cannot have with interfaces. The implementation of the type class is not a part of the definition of the type. In C#, to implement an interface, you must implement it as a part of the definition of the type that implements it. This means you may not implement an interface for a type which you do not implement yourself, however in Haskell you may implement a type class for any type you have access to.

That's probably the largest immediately, but there's another fairly significant difference that makes the C# equivalent really not work nearly as well, and you are touching on it in your question. It's about Polymorphism. Also there's some relatively generic things Haskell allows you to do with type classes which outright do not translate especially when you start looking at the amount of genericism in existential types or other GHC extensions like Generic ADTs.

You see, with Haskell you can define the functors

data List a = List a (List a) | Terminal
data Tree a = Tree val (Tree a) (Tree a) | Terminal

instance Functor List where
  fmap :: (a -> b) -> List a -> List b
  fmap f (List a Terminal) = List (f a) Terminal
  fmap f (List a rest) = List (f a) (fmap f rest)

instance Functor Tree where
  fmap :: (a -> b) -> Tree a -> Tree b
  fmap f (Tree val Terminal Terminal) = Tree (f val) Terminal Terminal
  fmap f (Tree val Terminal right) = Tree (f val) Terminal (fmap f right)
  fmap f (Tree val left Terminal) = Tree (f val) (fmap f left) Terminal
  fmap f (Tree val left right) = Tree (f val) (fmap f left) (fmap f right)

Then in consumption you can have a function:

mapsSomething :: Functor f, Show a => f a -> f String
mapsSomething rar = fmap show rar

Herein lies the problem. In C# how do you write this function?

public Tree<a> : Functor<a>
{
    public a Val { get; set; }
    public Tree<a> Left { get; set; }
    public Tree<a> Right { get; set; }

    public Functor<b> fmap<b>(Func<a,b> f)
    {
        return new Tree<b>
        {
            Val = f(val),
            Left = Left.fmap(f);
            Right = Right.fmap(f);
        };
    }
}

public string Show<a>(Showwable<a> ror)
{
    return ror.Show();
}

public Functor<String> mapsSomething<a,b>(Functor<a> rar) where a : Showwable<b>
{
    return rar.fmap(Show<b>);
}

So there's a couple things wrong with the C# version, for one thing I'm not even certain it will allow you to use the <b> qualifier like I did there, but without it I am certain it wouldn't dispatch Show<> appropriately (feel free to try and compile to find out; I didn't).

The bigger problem here however is that unlike above in Haskell where we had our Terminals defined as part of the type and then usable in place of the type, due to C# lacking appropriate parametric polymorphism (which becomes super obvious as soon as you try to interop F# with C#) you can't clearly or cleanly distinguish whether Right or Left are Terminals. Best you can do is use null, but what if you're trying to make a value type a Functor or in the case of Either where you're distinguishing two types that both carry a value? Now you have to use one type and have two different values to check and switch between to model your discrimination?

The lack of proper sum types, union types, ADTs, whatever you want to call them really makes a lot of what typeclasses give you fall away because at the end of the day they let you treat multiple types (constructors) as a single type, and .NET's underlying type system simply has no such concept.

Answer 2

What you need is two classes, one to model the higher order generic (the functor) and one to model the combined functor with the free value A

interface F<Functor> {
   IF<Functor, A> pure<A>(A a);
}

interface IF<Functor, A> where Functor : F<Functor> {
   IF<Functor, B> pure<B>(B b);
   IF<Functor, B> map<B>(Func<A, B> f);
}

So if we use the Option monad (because all monads are functors)

class Option : F<Option> {
   IF<Option, A> pure<A>(A a) { return new Some<A>(a) };
}

class OptionF<A> : IF<Option, A> {
   IF<Option, B> pure<B>(B b) {
      return new Some<B>(b);
   }

   IF<Option, B> map<B>(Func<A, B> f) {
       var some = this as Some<A>;
       if (some != null) {
          return new Some<B>(f(some.value));
       } else {
          return new None<B>();
       }
   } 
}

You can then use static extension methods to convert from IF<Option, B> to Some<A> when you need to