Take the 2-minute tour ×

I'm trying to translate the Haskell core library's Arrows into F# (I think it's a good exercise to understanding Arrows and F# better, and I might be able to use them in a project I'm working on.) However, a direct translation isn't possible due to the difference in paradigms. Haskell uses type-classes to express this stuff, but I'm not sure what F# constructs best map the functionality of type-classes with the idioms of F#. I have a few thoughts, but figured it best to bring it up here and see what was considered to be the closest in functionality.

For the tl;dr crowd: How do I translate type-classes (a Haskell idiom) into F# idiomatic code?

For those accepting of my long explanation:

This code from the Haskell standard lib is an example of what I'm trying to translate:

class Category cat where
    id :: cat a a
    comp :: cat a b -> cat b c -> cat a c
class Category a => Arrow a where

instance Category (->) where
    id f = f
instance Arrow (->) where
    arr f = f
    first f = f *** id

Attempt 1: Modules, Simple Types, Let Bindings

My first shot at this was to simply map things over directly using Modules for organization, like:

type Arrow<'a,'b> = Arrow of ('a -> 'b)

let arr f = Arrow f
let first f = //some code that does the first op

That works, but it loses out on polymorphism, since I don't implement Categories and can't easily implement more specialized Arrows.

Attempt 1a: Refining using Signatures and types

One way to correct some issues with Attempt 1 is to use a .fsi file to define the methods (so the types enforce easier) and to use some simple type tweaks to specialize.

type ListArrow<'a,'b> = Arrow<['a],['b]>
type ListArrow<'a,'b> = LA of Arrow<['a],['b]>

But the fsi file can't be reused (to enforce the types of the let bound functions) for other implementations, and the type renaming/encapsulating stuff is tricky.

Attempt 2: Object models and interfaces

Rationalizing that F# is built to be OO also, maybe a type hierarchy is the right way to do this.

type IArrow<'a,'b> =
    abstract member comp : IArrow<'b,'c> -> IArrow<'a,'c>
type Arrow<'a,'b>(func:'a->'b) = 
    interface IArrow<'a,'b> with
        member this.comp = //fun code involving "Arrow (fun x-> workOn x) :> IArrow"

Aside from how much of a pain it can be to get what should be static methods (like comp and other operators) to act like instance methods, there's also the need to explicitly upcast the results. I'm also not sure that this methodology is still capturing the full expressiveness of type-class polymorphism. It also makes it hard to use things that MUST be static methods.

Attempt 2a: Refining using type extensions

So one more potential refinement is to declare the interfaces as bare as possible, then use extension methods to add functionality to all implementing types.

type IArrow<'a,'b> with
    static member (&&&) f = //code to do the fanout operation

Ah, but this locks me into using one method for all types of IArrow. If I wanted a slightly different (&&&) for ListArrows, what can I do? I haven't tried this method yet, but I would guess I can shadow the (&&&), or at least provide a more specialized version, but I feel like I can't enforce the use of the correct variant.

Help me

So what am I supposed to do here? I feel like OO should be powerful enough to replace type-classes, but I can't seem to figure out how to make that happen in F#. Were any of my attempts close? Are any of them "as good as it gets" and that'll have to be good enough?

share|improve this question
"How do I translate type-classes (a Haskell idiom) into F# idiomatic code?" Bad idea. You should look at the problem you were trying to solve instead of the solution that happened to use type classes and figure out how to solve it using the feature that F# does provide. –  Jon Harrop Oct 29 '10 at 12:10
@Jon Harrop That's the point of the question. Haskell solves dozens of problems with Type Classes, and I wanted to know what the F# alternatives were to solving a similar class of problems. Also the Arrow port isn't to solve any problems, its just a "I thought it would be fun to learn more about Arrows" activity. –  CodexArcanum Oct 29 '10 at 14:37
Then I think it would be really valuable if you could explain some of the problems that type classes solve and ask people how they would solve the same problems in F#. –  Jon Harrop Oct 30 '10 at 13:21
@Gustavo I'd be glad to switch answers (I hadn't thought too much about this question in quite a while) but I don't completely follow your code. Does your method address the issues brought up in the first question, about higher kinded polymorphism? Like if I had an Arrow containing Monad types, would it all work? –  CodexArcanum Jun 7 '12 at 16:33
@CodexArcanum Yes, kind of. The inferred static constraints require some static methods to exist in the generic class. It works at method level, so it will work not only with Monads but with every class that has Return and Bind and eventually it may require only Return (as int the case of Id). –  Gustavo Jun 11 '12 at 9:22
add comment

2 Answers

up vote 17 down vote accepted

Here's the approach I use to simulate Typeclasses (from http://code.google.com/p/fsharp-typeclasses/ ).

In your case, for Arrows could be something like this:

let inline i2 (a:^a,b:^b     ) =                                                      
    ((^a or ^b      ) : (static member instance: ^a* ^b     -> _) (a,b  ))
let inline i3 (a:^a,b:^b,c:^c) =                                                          
    ((^a or ^b or ^c) : (static member instance: ^a* ^b* ^c -> _) (a,b,c))

type T = T with
    static member inline instance (a:'a      ) = 
        fun x -> i2(a   , Unchecked.defaultof<'r>) x :'r
    static member inline instance (a:'a, b:'b) = 
        fun x -> i3(a, b, Unchecked.defaultof<'r>) x :'r

type Return = Return with
    static member instance (_Monad:Return, _:option<'a>) = fun x -> Some x
    static member instance (_Monad:Return, _:list<'a>  ) = fun x  ->    [x]
    static member instance (_Monad:Return, _: 'r -> 'a ) = fun x _ ->    x
let inline return' x = T.instance Return x

type Bind = Bind with
    static member instance (_Monad:Bind, x:option<_>, _:option<'b>) = fun f -> 
        Option.bind  f x
    static member instance (_Monad:Bind, x:list<_>  , _:list<'b>  ) = fun f -> 
        List.collect f x
    static member instance (_Monad:Bind, f:'r->'a, _:'r->'b) = fun k r -> k (f r) r
let inline (>>=) x (f:_->'R) : 'R = T.instance (Bind, x) f
let inline (>=>) f g x    = f x >>= g

type Kleisli<'a, 'm> = Kleisli of ('a -> 'm)
let runKleisli (Kleisli f) = f

type Id = Id with
    static member        instance (_Category:Id, _: 'r -> 'r     ) = fun () -> id
    static member inline instance (_Category:Id, _:Kleisli<'a,'b>) = fun () ->
        Kleisli return'
let inline id'() = T.instance Id ()

type Comp = Comp with
    static member        instance (_Category:Comp,         f, _) = (<<) f
    static member inline instance (_Category:Comp, Kleisli f, _) =
        fun (Kleisli g) -> Kleisli (g >=> f)

let inline (<<<) f g = T.instance (Comp, f) g
let inline (>>>) g f = T.instance (Comp, f) g

type Arr = Arr with
    static member        instance (_Arrow:Arr, _: _ -> _) = fun (f:_->_) -> f
    static member inline instance (_Arrow:Arr, _:Kleisli<_,_>) = 
        fun f -> Kleisli (return' <<< f)
let inline arr f = T.instance Arr f

type First = First with
    static member        instance (_Arrow:First, f, _: 'a -> 'b) = 
        fun () (x,y) -> (f x, y)
    static member inline instance (_Arrow:First, Kleisli f, _:Kleisli<_,_>) =
        fun () -> Kleisli (fun (b,d) -> f b >>= fun c -> return' (c,d))
let inline first f = T.instance (First, f) ()

let inline second f = let swap (x,y) = (y,x) in arr swap >>> first f >>> arr swap
let inline ( *** ) f g = first f >>> second g
let inline ( &&& ) f g = arr (fun b -> (b,b)) >>> f *** g


> let f = Kleisli (fun y -> [y;y*2;y*3]) <<< Kleisli ( fun x -> [ x + 3 ; x * 2 ] ) ;;
val f : Kleisli<int,int list> = Kleisli <fun:f@4-14>

> runKleisli f <| 5 ;;
val it : int list = [8; 16; 24; 10; 20; 30]

> (arr (fun y -> [y;y*2;y*3])) 3 ;;
val it : int list = [3; 6; 9]

> let (x:option<_>) = runKleisli (arr (fun y -> [y;y*2;y*3])) 2 ;;
val x : int list option = Some [2; 4; 6]

> ( (*) 100) *** ((+) 9)   <| (5,10) ;;
val it : int * int = (500, 19)

> ( (*) 100) &&& ((+) 9)   <| 5 ;;
val it : int * int = (500, 14)

> let x:List<_>  = (runKleisli (id'())) 5 ;;
val x : List<int> = [5]

Note: use id'() instead of id

Update: you need F# 3.0 to compile this code, otherwise here's the F# 2.0 version.

And here's a detailed explanation of this technique which is type-safe, extensible and as you can see works even with some Higher Kind Typeclasses.

share|improve this answer
Out of curiosity, what's F# 3.0 specific on this code? –  Gustavo Guerra Mar 13 '13 at 11:21
@GustavoGuerra Function i3 will not compile in F# 2.0 because of a parser bug. There is a workaround using operators, but the code become less readable. –  Gustavo Aug 16 '13 at 9:32
add comment

My brief answer is:

OO is not powerful enough to replace type classes.

The most straightforward translation is to pass a dictionary of operations, as in one typical typeclass implementation. That is if typeclass Foo defines three methods, then define a class/record type named Foo, and then change functions of

Foo a => yadda -> yadda -> yadda

to functions like

Foo -> yadda -> yadda -> yadda

and at each call site you know the concrete 'instance' to pass based on the type at the call-site.

Here's a short example of what I mean:

// typeclass
type Showable<'a> = { show : 'a -> unit; showPretty : 'a -> unit } //'

// instances
let IntShowable = 
    { show = printfn "%d"; showPretty = (fun i -> printfn "pretty %d" i) }
let StringShowable = 
    { show = printfn "%s"; showPretty = (fun s -> printfn "<<%s>>" s) }

// function using typeclass constraint
// Showable a => [a] -> ()
let ShowAllPretty (s:Showable<'a>) l = //'
    l |> List.iter s.showPretty 

// callsites
ShowAllPretty IntShowable [1;2;3]
ShowAllPretty StringShowable ["foo";"bar"]

See also


share|improve this answer
Also, I find it funny that when I first got into Haskell, I thought type-classes were crappy Interfaces with bad encapsulation; and now I'm starting to think Objects are crappy type-classes with poor polymorphism. "They" were right when I read that learning FP will ruin you for OOP. –  CodexArcanum Oct 27 '10 at 15:32
Ah, I had seen that blog post before but not given it a good read, time to correct that I suppose. Thanks for the link. Also here is the blog post I mentioned about Matrices: fdatamining.blogspot.com/2010/03/… He also talks about the INumerics interface. And yeah, your link has it right, Monads (and Arrows) are a lot less useful if you can't properly abstract the basic operations on them. –  CodexArcanum Oct 27 '10 at 15:37
This technique is not too bad for a typeclass like Show. However, I haven't seen any good techniques for when higher kinds are needed (e.g. in the original question, cat is of kind * => * => *, which can't be cleanly represented in .NET). –  kvb Oct 27 '10 at 16:19
I don't think this technique can work for higher-kinded types. .NET type system does not support higher-kinded polymorphism like Haskell. –  snk_kid Oct 27 '10 at 18:52
No, the method Brian presents will break down rather quickly when you start adding types that are themselves generic (higher-kinded). It seems the only recourse is the dictionary lookup method if type-class polymorphism is needed, or just manually writing out everything with lots of duplication to get all the functionality wired up. –  CodexArcanum Oct 27 '10 at 20:07
show 3 more comments

Your Answer


