Where F#/.NET Falls Short: Higher Kinds

Every programmer thinks their favorite language has a problem. I am no exception. I used to think that F# misses an ML module system or Haskell-style typeclasses, but I came to realize that the complaint is really about a feature called higher-kinded polymorphism. Without this feature, there is a lot of very beautiful, general, and type-safe code in OCaml and Haskell that cannot be expressed in type-safe F#. It can be expressed, but you are facing a tradeoff:

• Sacrifice generality – this is what workflow builders do. In effect, F# has no true monads, because you cannot easily write code generalized over an arbitrary monad.
  
• Sacrifice type safety by using downcasts and rely on convention.

Option #1 is by far the most popular, but very detrimental to the F# ecosystem, as it encourages duplication of specific code that could have otherwise been expressed by a single, general definition.

Option #2 is controversial. I have attempted a few encodings I personally have not yet found a practical one, and in practice usually fall back to Option #1.

To illustrate, suppose we have this Haskell code:

	class Functor f where
	fmap :: (a -> b) -> f a -> f b
	instance Functor [] where
	fmap = map

view raw Functor.hs hosted with ❤ by GitHub

Functor type class is parameterized over f, which is itself generic. This is exactly the piece that .NET and F# are lacking. If one really insists on writing code that is generic in every possible Functor, not just a concrete Functor instance, one ends up having to rely on downcasts and convention:

	type Box<'T1,'T2> = { Value : obj }
	module List =
	let Box (list: list<'T>) : Box<list<obj>,'T> = { Value = list }
	let Unbox (x: Box<list<obj>,'T>) : list<'T> = x.Value :?> _
	type IFunctor<'T> =
	abstract member Map : ('T1 -> 'T2) -> Box<'T,'T1> -> Box<'T,'T2>
	let ListFunctor =
	{
	new IFunctor<list<obj>> with
	member this.Map f x =
	List.Box << List.map f << List.Unbox <| x
	}

view raw Functor.fs hosted with ❤ by GitHub

As you can see, this approach (1) has a run-time cost and (2) gets annoying very quickly as the complexity of the code grows.

It is sad.