# How would I translate a Haskell type class into F#?

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

https://web.archive.org/web/20081017141728/http://blog.matthewdoig.com/?p=112

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
arr :: (b -> c) -> a b c
first :: a b c -> a (b,d) (c,d)
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]>
//or
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?

Here's the same answer but without operators. It works only in F# 3.0 and you can use any number of parameters.

```
let inline i3 (a:^a,b:^b,c:^c) = ((^a or ^b or ^c) : (static member threeParams: ^a* ^b* ^c -> _) (a,b,c))
open Symbolism
type MathObjectOverloads =
| MathObjectOverloads
static member threeParams (MathObjectOverloads, a: #MathObject , b: int ) = MathObject.op_ExclusiveOr(a, b)
static member threeParams (MathObjectOverloads, a: #MathObject , b: #MathObject) = MathObject.op_ExclusiveOr(a, b)
static member threeParams (MathObjectOverloads, a: System.Int32, b: #MathObject) = MathObject.op_ExclusiveOr(a, b)
let inline ( ** ) a b = i3(MathObjectOverloads, a, b)
```

## F# Generic methods and operators

Standard .NET generics are not expressive enough to allow this kind of generic functions. The problem is that your code can work for any `'a`

that supports the subtraction operator, but .NET generics cannot capture this constraint (they can capture interface constraints, but not member constraints).

However you can use F# `inline`

functions and statically resolved type parameters that can have additional member constraints. I wrote an article that provides some more details about these.

Briefly, if you mark the function as `inline`

and let the compiler infer the type, then you get (I removed explicit mention of the type parameter, as that makes the situation trickier):

```
> let inline genericDiff h (f: float -> _) x =
> ((f (x + h)) - (f (x - h))) / (h * 2.0);;
val inline genericDiff :
float -> (float -> ^a) -> float -> float
when ^a : (static member ( - ) : ^a * ^a -> float)
```

The compiler now used `^a`

instead of `'a`

to say that the parameter is resolved statically (during inlining) and it added a constraint saying that `^a`

has to have a member `-`

that takes two *things* and returns `float`

.

Sadly, this is not quite what you want, because your `-`

operator returns `Vect3`

(and not `float`

as the compiler inferred). I think the problem is that the compiler wants `/`

operator with two arguments of the same type (while yours is `Vect3 * float`

). You can use different operator name (for example, `/.`

):

```
let inline genericDiff2 h (f: float -> _) x =
((f (x + h)) - (f (x - h))) /. (h * 2.0);;
```

In this case, it will work on `Vect3`

(if you rename the scalar division), but it won't *easilly* work on `float`

(though there may be hacks that will make that possible - see this answer - though I would not consider that idiomatic F# and I'd probably try to find a way to avoid the need for that). Would it make sense to provide elementwise division and pass `h`

as `Vect3`

value, perhaps?

For some reason the compiler assumes the type signature of division is

`^a*^a -> ^b`

when it should be okay for it to be

`^a*^c -> ^b`

I believe this is implied by 9.7 in the spec (this is for units of measure but I don't see why they are a special case). If division could have the desired type signature you could do:

```
let inline genericDiff h (f: float -> ^a) x =
let inline sub a b = (^a: (static member (-):^a * ^a-> ^a) (a,b))
let inline div a b = (^a: (static member (/):^a -> float-> ^c) (a,b))
div (sub (f (x+h)) (f(x-h))) (h*2.0)
```

I have included implicit `sub`

and `div`

but they shouldn't be required - the idea is to make the signature explicit.

I believe the fact that this does not allow `^a`

to be anything but a float may in fact be a bug.

This is inspired by a toolbox of functional higher-order idioms I once implemented. Back then I found the corner cases agonizing, I still do today:) Also, finding good names is always an issue...

Consider meta-predicate `mapadj/4`

:

```
mapadj(Relation_4,As,Bs,Cs) :-
list_list_list_mapadj(As,Bs,Cs,Relation_4).
list_list_list_mapadj([],[],[],_).
list_list_list_mapadj([A|As],Bs,Cs,Relation_4) :-
list_prev_list_list_mapadj(As,A,Bs,Cs,Relation_4).
list_prev_list_list_mapadj([],_,[],[],_).
list_prev_list_list_mapadj([A1|As],A0,[B|Bs],[C|Cs],Relation_4) :-
call(Relation_4,A0,A1,B,C),
list_prev_list_list_mapadj(As,A1,Bs,Cs,Relation_4).
```

Sample uses:

```
z_z_sum_product(X,Y,Sum,Product) :-
Sum #= X + Y,
Product #= X * Y.
:- mapadj(z_z_sum_product,[], [], []).
:- mapadj(z_z_sum_product,[1], [], []).
:- mapadj(z_z_sum_product,[1,2], [3], [2]).
:- mapadj(z_z_sum_product,[1,2,3], [3,5], [2,6]).
:- mapadj(z_z_sum_product,[1,2,3,4],[3,5,7],[2,6,12]).
```

I'm aware of the rift in the corner cases `As = []`

and `As = [_]`

, still I feel this is as close to "for all adjacent list items" as it gets.

Also, all of this can easily be extended:

- down to
`mapadj/2`

(akin to`chain/2`

, except for the type-check with singleton lists) - sideways, with an additional state argument, to
`foldadjl/n`

,`scanadjl/n`

Regarding names: IMO the `l`

/ `r`

suffix is required with `fold`

/ `scan`

, but not with `map`

.

### Edit 2015-04-26

Here comes the before-mentioned `foldadjl/4`

:

```
foldadjl(Relation_4,Xs) -->
list_foldadjl(Xs,Relation_4).
list_foldadjl([],_) -->
[].
list_foldadjl([X|Xs],Relation_4) -->
list_prev_foldadjl(Xs,X,Relation_4).
list_prev_foldadjl([],_,_) -->
[].
list_prev_foldadjl([X1|Xs],X0,Relation_4) -->
call(Relation_4,X0,X1),
list_prev_foldadjl(Xs,X1,Relation_4).
```

### Edit 2015-04-27

Here comes meta-predicate `splitlistIfAdj/3`

, based on
`if_/3`

which was proposed in a previous answer
on reification.

```
split_if_adj(P_3,As,Bss) :- splitlistIfAdj(P_3,As,Bss).
splitlistIfAdj(P_3,As,Bss) :-
list_split_(As,Bss,P_3).
list_split_([],[],_).
list_split_([X0|Xs], [Cs|Bss],P_3) :-
list_prev_split_(Xs,X0,Cs,Bss, P_3).
list_prev_split_([], X, [X],[],_).
list_prev_split_([X1|Xs],X0,[X0|Cs],Bss,P_3) :-
if_(call(P_3,X0,X1),
(Cs = [], Bss = [Cs0|Bss0]),
(Cs = Cs0, Bss = Bss0)),
list_prev_split_(Xs,X1,Cs0,Bss0,P_3).
```

To show it in use let's define `dif/3`

exactly the same way as `(=)/3`

but with flipped truth-value:

```
dif(X, Y, R) :- X == Y, !, R = false.
dif(X, Y, R) :- ?=(X, Y), !, R = true. % syntactically different
dif(X, Y, R) :- X \= Y, !, R = true. % semantically different
dif(X, Y, R) :- R == false, !, X = Y.
dif(X, X, false).
dif(X, Y, true) :-
dif(X, Y).
```

Now we use them in tandem:

```
?- splitlistIfAdj(dif,[1,2,2,3,3,3,4,4,4,4],Pss).
Pss = [[1],[2,2],[3,3,3],[4,4,4,4]]. % succeeds deterministically
```

What if we generalize some list items? Do we get multiple answers with the right pending goals?

First, a small example:

```
?- splitlistIfAdj(dif,[1,X,2],Pss).
X = 1, Pss = [[1,1],[2]] ;
X = 2, Pss = [[1],[2,2]] ;
dif(X,1),dif(X,2), Pss = [[1],[X],[2]].
```

A somewhat bigger example involving the two variables `X`

and `Y`

.

```
?- splitlistIfAdj(dif,[1,2,2,X,3,3,Y,4,4,4],Pss).
X = 2, Y = 3, Pss = [[1],[2,2,2],[3,3,3],[4,4,4]] ;
X = 2, Y = 4, Pss = [[1],[2,2,2],[3,3],[4,4,4,4]] ;
X = 2, dif(Y,3),dif(Y,4), Pss = [[1],[2,2,2],[3,3],[Y],[4,4,4]] ;
X = Y, Y = 3, Pss = [[1],[2,2],[3,3,3,3],[4,4,4]] ;
X = 3, Y = 4, Pss = [[1],[2,2],[3,3,3],[4,4,4,4]] ;
X = 3, dif(Y,3),dif(Y,4), Pss = [[1],[2,2],[3,3,3],[Y],[4,4,4]] ;
dif(X,2),dif(X,3), Y = 3, Pss = [[1],[2,2],[X],[3,3,3],[4,4,4]] ;
dif(X,2),dif(X,3), Y = 4, Pss = [[1],[2,2],[X],[3,3],[4,4,4,4]] ;
dif(X,2),dif(X,3), dif(Y,3),dif(Y,4), Pss = [[1],[2,2],[X],[3,3],[Y],[4,4,4]].
```

### Edit 2015-05-05

Here's `tpartition/4`

:

```
tpartition(P_2,List,Ts,Fs) :- tpartition_ts_fs_(List,Ts,Fs,P_2).
tpartition_ts_fs_([],[],[],_).
tpartition_ts_fs_([X|Xs0],Ts,Fs,P_2) :-
if_(call(P_2,X), (Ts = [X|Ts0], Fs = Fs0),
(Ts = Ts0, Fs = [X|Fs0])),
tpartition_ts_fs_(Xs0,Ts0,Fs0,P_2).
```

Sample use:

```
?- tpartition(=(0), [1,2,3,4,0,1,2,3,0,0,1], Ts, Fs).
Ts = [0, 0, 0],
Fs = [1, 2, 3, 4, 1, 2, 3, 1].
```

### Edit 2015-05-15

On and on, ... here's `splitlistIf/3`

:

```
split_if(P_2,As,Bss) :- splitlistIf(P_2,As,Bss).
splitlistIf(P_2,As,Bss) :-
list_pred_split(As,P_2,Bss).
list_pred_split([],_,[]).
list_pred_split([X|Xs],P_2,Bss) :-
if_(call(P_2,X), list_pred_split(Xs,P_2,Bss),
(Bss = [[X|Ys]|Bss0], list_pred_open_split(Xs,P_2,Ys,Bss0))).
list_pred_open_split([],_,[],[]).
list_pred_open_split([X|Xs],P_2,Ys,Bss) :-
if_(call(P_2,X), (Ys = [], list_pred_split(Xs,P_2,Bss)),
(Ys = [X|Ys0], list_pred_open_split(Xs,P_2,Ys0,Bss))).
```

Let's use it:

```
?- splitlistIf(=(x),[x,1,2,x,1,2,3,x,1,4,x,x,x,x,1,x,2,x,x,1],Xs).
Xs = [[1, 2], [1, 2, 3], [1, 4], [1], [2], [1]].
```