## Introduction

It seems natural that when learning a new programming people try and apply
concepts or practices which they've experienced before in other languages.
Before learning F# I, like many people, had toyed with Haskell so part of
getting to grips with F# was going though the process of reimplementing some of
the types and functions I'd come across in Haskell into F#. Firstly, the
**Maybe** type.

```
type Maybe<'a> =
| Just of 'a
| Nothing
```

Once I'd defined the type then it was natural to define the functor and monadic operations for the type.

```
let fmap f v =
match v with
| Just x -> Just (f x)
| Nothing -> Nothing
let return' v = Just v
let bind v f =
match v with
| Just x -> f x
| Nothing -> Nothing
let ( >>= ) = bind
```

And finally, we can define a computation expression builder for our type.

```
type MaybeBuilder() =
member x.Bind(v,f) = bind v f
member x.Return v = return' v
let maybe = MaybeBuilder()
```

And we can quite happily use this new type and computation expression.

```
let result =
maybe {
let! x = Just 1
let! y = Nothing
return 5
}
```

This all works very nicely. However, I started to have issues when defining an
**Either** type. F# does not support function overloading based on the function
parameter types, so I could not redefine **fmap**, **return'** or
**bind**/**>>=** unless I put these definitions in their own module,
seperate from the definitions for **Maybe**. Even though each type will have
it's own implementation of, say, **bind**, it might still be nice to have a single
definition of **>>=** which is "overloaded" for each monadic type. It's
at this point that I started trying to use interfaces to replicate Haskell's
typeclasses and came up against a brick wall. The interface that I'd need to
declare would look something like this:

```
public interface IMonad<M, A>
{
M<B> Bind<B>(M<A> m, Func k);
M<A> Return(A a);
}
```

Unfortunately, this interface definition will not compile. The CLR type system is not capable of representing this type of construct. An excellent article explaining why this is the case can be found on Joe Duffy's blog (the original link seems to be broken so here's the google cache version).

## Statically resolved type parameters to the rescue

I ended up abandoning this experiment for a while in favour of looking at other areas of the F# language and I eventually came across statically resolved type parameters. A statically resolved type parameter is exactly what it sounds like, a type that is resolved and replaced at compile time as opposed to run time. Crucially, statically resolved type parameters can have interesting constraints placed upon them. Here's a slightly contrived example:

```
type TypeA = | TypeA of int
with member x.GetVal = match x with TypeA v -> v
// Declaration with a statically resolved type parameter.
// We require that the parameter 'a' be of type ^a.
// We then constrain ^a such that it must have a member function
// named GetVal that takes no parameters and returns an integer.
// We then apply this statically resolved function to the parameter 'a'
// to yield the integer that was wrapped in TypeA. We can now increment
// and return the number.
let inline increment (a : ^a) : int =
let v1 = (^a : (member GetVal : int) a)
v1 + 1
let t1 = TypeA 1
let result = increment t1
```

The only constraint we placed upon the increment function was that the parameter
**a** have a member named **GetVal** that returns an integer. We can pass any
parameter to this function that fullfills this constraint. The following is
still perfectly valid:

```
// Declare a new type that satisfies the type constraint for increment
type SomeOtherType = SomeOtherType
with member x.GetVal = (new System.Random()).Next()
let t2 = SomeOtherType
let result2 = increment t2
```

The ability to constrain an argument by the members it defines is called structural typing or, more colloquially, duck typing.

Armed with our new knowledge of statically resolved type parameters is it possible to define to a single function that can be applied to arguments of both Maybe and Either types? Yes:

```
// Single definition of each of our Monadic functions. Each is constrained
// to require the supplied monadic type to define a doReturn or a
// doBind function.
let inline return' (v : ^a) : ^b =
(^b : (static member doReturn : ^a -> ^b) v)
let inline bind (v : ^a) (f : ^b) =
(^a : (static member doBind : ^a -> ^b -> ^c ) v,f)
let inline (>>=) v f = bind v f
type Maybe<'a> =
| Nothing
| Just of 'a
static member inline doReturn(v) = Just v
static member inline doBind(v,f) =
match v with
| Just v' -> f v'
| Nothing -> Nothing
type Either<'a, 'b> =
| Left of 'a
| Right of 'b
static member inline doReturn(v) = Right v
static member inline doBind(v,f) =
match v with
| Right v' -> f v'
| Left v' -> Left v'
let m1 = (Just 1) >>= (fun x -> return' (x + 1)) >>= (fun x ->return' (x.ToString()))
let e1 = (Right 1) >>= (fun x -> return' (x + 1)) >>= (fun x ->return' (x.ToString()))
```

Our bind function, **>>=** can be successfully applied to both Either and
Maybe types. It's now possible to simulate Haskells do-notation with a single
definition of a **DoBuilder**:

```
type DoBuilder() =
member inline x.Bind (v,f) = bind v f
member inline x.Return v = return' v
let do' = DoBuilder()
let mTest =
do'{
let! a = (Just 1)
return a
}
let eTest : Either<string, int> =
do'{
let! a = (Right 1)
return a
}
```

## Conclusion

For me, this was an interesting learning exercise into some of F#'s lesser well-known capabilities. Whilst it's possible to replicate some of the power of typeclasses I get the feeling that the resulting F# is somewhat un-idiomatic. Having said that, a similar approach has been used in the fsharpx library.