In my opinion type classes are not really helpful without higher-kind generics abstraction. And F# does not have that, nor does .NET. In fact, I would probably be more happy with ML-style modules (and their flavor of higher kinds) than with type classes. If I were to design a better language than F# right now, I would go for OCaml-like core with modules (and therefore higher-kinded generics), and I would probably opt for the modules to be erased by abstract interpretation like MLton does. This would leave core ML which the compiler could then handle the same way as F#.

The problem with F# is the extra complexity of objects and subtyping. Treating F# extended with higher kinds and modules formally in presence of OO sounds like a real challenge. Again, if you ask me, I'd throw OO out..

By on 12/7/2011 10:29 AM ()

I agree, if at some point the F# team decides to implement Typeclasses at CLR level or at least as an F# compiler feature, they should first upgrade the type system in order to support Higher Kinds.

However the technique I use still allowed me to define (kind-of) typeclasses of higher kind types like Monad, Category, etc.
But it's true that becomes a little bit tricky to figure out how to specify types for Haskell wrappers (i.e. Kleisli) with a "hat" type, where the original type is HK.

By on 12/9/2011 3:11 PM ()

Adding HK types to the CLR is a popular request, but has been officially declined by MS.

By on 2/14/2012 8:37 AM ()

Just looked at your code. Inlining is nice. However, here:

1
2
3
4
5

type Ap = Ap with
static member (?<-) (f:option<_>, _Applicative:Ap, x:option<_>) = ap f x
static member (?<-) (f:list<_>  , _Applicative:Ap, x:list<_>  ) = ap f x
static member (?<-) (f:IO<_>    , _Applicative:Ap, x          ) = ap f x
static member (?<-) (f:_ -> _   , _Applicative:Ap, g: _ -> _  ) = ap f g

Does not this mean that one can't add new instances without recompiling the whole project? That would be a deal-breaker for me at least. The point is code reuse: if instance set is fixed, you can't reuse nice functions like sequence for arbitrary monads.

By on 12/9/2011 3:28 PM ()

You can add instances later, in another module or even another assembly, that's not a problem, except if you try to add an instance outside it's own type definition, see my previous answer about the orphan instances limitation.
That code could be perfectly split this way:

1
2
3
4
5

type Ap = Ap with
static member (?<-) (f:option<_>, _Applicative:Ap, x:option<_>) = ap f x
static member (?<-) (f:list<_>  , _Applicative:Ap, x:list<_>  ) = ap f x
static member (?<-) (f:_ -> _   , _Applicative:Ap, g: _ -> _  ) = ap f g
let inline (<*>) x y = x ? (Ap) <- y

in another module

1
2
3
4
5
6

type IO<'a> = IO of (unit->'a) with
// ...  implement Bind and Return
static member (?<-) (f:IO<_>    , _Applicative:Ap, x          ) = ap f x
// ...

// now you can use <*> with IO

But for  option , list and  (->)  you can't because they're already defined, so either you add the instances in the Ap definition or you do it later with a wrapper type (as I did with ZipList in that project).

See the example in the section Adding new instances to existing Typeclasses

In short: yes, you will be able to re-use sequence without recompiling, as long as new operators as static member come into scope, because they will be included in the operator overloading resolution.
If you find errors while trying to do this please tell me, I will be interested to be able to reproduce it.

By on 12/9/2011 4:41 PM ()

Nice! Did not realize this.

By on 12/12/2011 8:56 AM ()

Could you explain what type classes would be like in F# without higher-kinded types? I always thought have the former required the latter. Would they be useful at all?

Also, do you know of any resources that compare the type class approach of Haskell to the module approach of Ocaml? I'd like to fully understand the trade-offs.

Thank you!

By on 12/7/2011 10:11 PM ()

Without higher kinds type classes could be somewhat useful, since F#'s primary problem is lack of HK not TC I think we should look in that direction first.

In Haskell parlance, for example, without HK, Monad and even Functor classes are not definable. Num and Eq are definable. This can be useful of course in its own way. But I maintain that the biggest problem is lack of HK and therefore true monads. ML easily has true monads with modules.

There is a nice proposal to integrate TC into the ML module system that also compares TC and modules, see the Modular Type Classes paper:

Disclaimer: I may sound like an expert but I am not (yet) one, I have not yet implemented either TC or even ML modules myself.

By on 12/8/2011 7:23 AM ()

I have seen lots of people thinking about typeclasses for F# lately, and have wondered if it would be possible to implement it elegantly using macros (see my blog post). The good thing about macros that could help with typeclasses, is that you can have short and readable code, while the compiler actually does a lot of work. This means that the solution doesn't have to be simple, as long as a computer can generate code to make it work.

By on 12/7/2011 1:32 AM ()

By on 12/10/2011 8:00 AM ()

I really want to see type-classes in .net but I think you have to support them at CLR-level to make them work

By on 1/12/2011 11:37 PM ()

I would like to share my approach to Typeclasses in F#.
It doesn't work at CLR level but it's type-safe because it works at compile-time.
I use inline functions and operators (in fact just one) to avoid writing ugly "when" constraints.
Playing with this technique I was able to define most Typeclasses from Haskell including Monad Transformers.
I have a post here that explains the approach and a project at code.google that mimics Haskell Typeclasses using this technique, which I use sometimes as base library for my F# projects.

By on 12/6/2011 12:35 PM ()

This is a very interesting workaround indeed.

I played with it a little, and I found that the following also works:

1
2
3
4
5
6
7

#nowarn "64"
type Fmap = Fmap with
static member fmap (Fmap, x : option<'a>) = fun f -> Option.map f x
static member fmap (Fmap, x : list<'a>) = fun f -> List.map f x

let inline fmap f x =
((^a or ^b) : (static member fmap : ^a * ^b -> _) (Fmap, x)) f

It's a little more verbose and requires a nowarn to compile flawlessly; but it avoids the need to use operators. This should remove the limitation of two polymorphic parameters, in case someone ever needs a typeclass with many parameters.

I believe it would also make it readable enough to have several methods in the same class, like this:

1
2
3
4
5
6
7
8
9

type Monad = Monad with
static member return' (Monad, _ : 'a option) = fun (x:'a) -> Some x
static member bind (Monad, x : 'a option) = fun f -> Option.bind f x

let inline return' x =
((^a or ^b) : (static member return' : ^a * ^b -> _)
let inline (>>=) x f = ((^a or ^b) : (static member bind : ^a * ^b -> _)
(Monad, x)) f
By on 12/22/2011 8:32 AM ()

Thanks a lot for your suggestion.
Indeed I'm spending lot of time trying to figure out how to get rid of the operators using techniques like this.
I would love to write code that way, I agree with you it's much more readable.
But while for basic stuff like bind and return works fine, when you get into Monad Transformers, Arrows things get more complicated and some static constraints get solved before hand.
I think the main problem is the inability to specify a triple or constraint, something like:
(^a or ^b or ^c).
The only way I found at the moment to generate it is using the ternary operator.
I will keep researching, more suggestions are welcome.
Feel free to clone the fsharp-typeclasses project and try to re-write the code in a better way.

By on 2/14/2012 12:46 AM ()

This is one of the coolest workarounds I've seen. I played with this technique a bit but still haven't been able to make it extensible, as type extensions can't provide operator overloads. Example: [link:gist.github.com]
What am I missing?
BTW do you know any other F# programmers in Argentina? Maybe we could form a user group...

By on 12/7/2011 2:03 PM ()

Thanks a lot for your feedback, I don't know any F# developer in Argentina (I live in Switzerland).

I'm not extending with Extension methods.
Extensions methods don't fit in this approach.
Maybe it's confusing, because the example I have in the post defines the type IO, then some variables, then it re-takes the IO type definition and finish defining the overloads for IO.
Despite it uses the same syntax as Extension Methods F# compiles them as normal methods because they are in the same module as the type definition.

The instance methods should be defined either in the Typeclass definition or in the Type definition.
In your code you don't include List in the Fmap type and you don't have the source code for List to add the overload there.

Basically what you' re trying to define is like an orphan instance in Haskell. I'm not sure if it's impossible to implement* but anyway even in Haskell is not a good practice.
Of course you can extend it with a wrapper type (i.e. ZipList), but instances for native types should be defined in the typeclass definition.

Have a look at the Script I have in the project with tests.
There you'll find samples with some new instance definitions for new types.

(*) Maybe there is a way to support orphan instances given that I was able to extend F# binary operators using the ternary operator.
I played a bit using this technique but still don't get the right static member constraints.
The main problem I face here is that F# don't compile when it finds more that one matching overload.
It will be fine if it just take the most specific definition, or even the first one and then issue a warning.

By on 12/7/2011 3:00 PM ()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

open System

type TypeClass<'a> =
static member Instance = Unchecked.defaultof<'a>

type TypeClassAttribute() =
inherit Attribute()

[<AbstractClass>]
type Eq<'a when 'a :> IComparable<'a>> =
member x.AreEqual (a: 'a) b = a.CompareTo b = 0

type Vector2D<'a when 'a:> IComparable<'a>>(x: 'a, y: 'a) =
typeclass eq = Eq<'a>

member this.X = x
member this.Y = y

member this.TypeClassEq(other: Vector2D<'a>) =
AreEqual x other.X && AreEqual y other.Y
override this.ToString() = "(" + x.ToString() + "; " + y.ToString() + ")"

let a = Vector2D(1, 0)
let b = Vector2D(1, 0)
let c = Vector2D(0, 1)

printfn "%A = %A is %b" a b (a.TypeClassEq b)
printfn "%A = %A is %b" a c (a.TypeClassEq c)
Console.ReadKey() |> ignore

This code now prints: (1; 0) = (1; 0) is true
(1; 0) = (0; 1) is false

It uses stubs for TypeClass<'a>.Instance and TypeClassAttribute since I've not added their implementation to FSharp.Core.
It seems for me a bit strange that this code works, because eq should be null. Looks like F# emits call instruction to do an instance call (C# emits callvirt to check if this poiter is not null).

1
2
3

typeclass eq = Eq<'a> expands to
[<TypeClass>]
static let eq = TypeClass<eq<'a>>.Instance

and AreEqual is searched among eq members since it can't be resolved and typechecked itself.

This is just a proof of concept. I'm going to replace 'typeclass' with 'constraint' to preserve compatibility with old code, add instance member lookup and do something with the fact that in F# expression 'a + b' (+) has type 'a -> 'a -> 'a, but in C# it would has type 'a * 'a -> 'a. Finally, type class checking must be implemented at compile time.

Suggestions and critics are welcome.

By on 1/9/2011 4:39 AM ()

Here is an example source, note Arithmetics has default constructor and MathExt provides (+) operator for int type (resolution does not add it by now):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

[<AbstractClass>]
type Arithmetics<'a> () =
abstract member (+): 'a * 'a -> 'a

[<TypeClassExtension>]
type MathExt =
static member (+)(a, b) = (+) a b

type Vector2D<'a>(x: 'a, y: 'a) =
typeclass ar = Arithmetics<'a>
member this.X = x
member this.Y = y

override this.ToString() = "(" + x.ToString() + "; " + y.ToString() + ")"

static member (+)(v1: Vector2D<'a>, v2: Vector2D<'a>) =
let a = Vector2D(ar.(+)(v1.X, v2.X), (+) (v1.Y, v2.Y))
// 1 + 1 |> ignore
a

let a = Vector2D(1, 0)
let b = Vector2D(-5, -14)
printfn "%A + %A = " a b
printfn "%A" (a+b)

Still no typeclass constraint check is done at compile time, just syntactic sugar.

By on 1/10/2011 4:44 AM ()

Did you make changes to the compiler's code generation, or does it call into the reflection-based implementation that you posted at ntypeclasses.codeplex.com?

I think any useful type classes implementation needs to get around the problem of adding two numbers: that is, emitting the add opcode when adding two doubles or ints, and calling into the right op_Addition method everywhere else. This could work if you only referenced type classes implemented inside the same assembly (and let inline lets you go part of the way), but exposing enough information about type classes in the assembly metadata could be a lot of work.

By on 11/29/2010 5:07 AM ()

I've not made working changes to the compiler yet. And I'm not currently going to use add opcode or F#'s inline because it would break compatibility with other .NET languages.

I've not tested NTypeClasses's performance yet. In this particular case an adequate JIT optimization would be way better than manual replacing method calls with an add instruction in F# compiler. I hope it has already been done by CLR team. In case it hasn't, we can always vote for it on Microsoft Connect.

Since TypeClass<t>.Instance refers to static readonly field it is possible in theory to inline all calls to its methods. This is also very important because in this case it is possible to replace virtual method calls with ordinary ones.

By on 11/29/2010 6:48 AM ()