# Notes on Standard ML

## Ad Hoc Polymorphism in SML

I recently started learning SML, and among the first tools I have needed to reach for were functor and monad instances for some simple SML collection types. This led me to signatures and structures.

Consider the following:

``````val xs = [1,2,3]
fun plusOne(x) = x + 1``````

To apply `plusOne` to each element in `xs`, we can use `List#map` from the SML Basis Library:

``val xs2 = List.map(plusOne)(xs) (* [2,3,4] *)``

The type of `List#map` is `('a -> 'b) -> 'a list -> 'b list`.

But what if we didn't have access to `List#map`, or if we wanted a way to generalize `map` to a common interface? We can define such an interface using a `signature`:

``````signature Functor =
sig
type 'a t
val map: ('a -> 'b) -> 'a t -> 'b t
end``````

This signature says that a `Functor` abstracts over some type constructor `t` to implement a `map` function that applies a function of type `'a -> 'b` for arbitrary types `'a` and `'b` to whatever `'a` means in `t` to produce a `'b t`.

That's a lot of alphabet soup, so let's be more concrete. To implement a signature, we write a `structure`:

``````structure ListFunctor:Functor =
struct
type 'a t = 'a list
val map = fn f => fn xs => List.map(f)(xs)
end``````

This structure implements a `Functor` where `t` is `list`. This lets us apply `'a -> 'b` to each element in a `'a list`, resulting in a `'b list`. Behind the scenes we just defer to `List#map`.

Now we can use it to map `plusOne` over `xs`:

``val xs2 = List.map(plusOne)(xs) (* [2,3,4] *)``

Now let's see if we can extend this and make a monad for lists. Here's our signature:

``````signature Monad =
sig
include Functor
val flatMap: 'a t -> ('a -> 'b t) -> 'b t
end``````

This signature extends `Functor` using the `include` keyword, and adds an additional function definition, `flatMap`, which is nearly the same as `map`, except that the function being applied returns a `'b t` instead of a flat `'b`.

To implement `flatMap` for lists, we can't delegate directly to any single `List` function, but we can cheat by combining `List#map` with `List#concat`:

``````structure ListMonad:Monad =
struct
open ListFunctor
val flatMap = fn xs => fn f => List.concat(List.map(f)(xs))
end``````

The type of `List#concat` is `'a list list -> 'a list`.

This structure extends `ListFunctor` using the `open` keyword, and implements `flatMap` by first mapping `f` over `xs`, and then flattening the resulting list of lists.

Here's what using `flatMap` looks like:

``````fun repeat(x) = [x,x,x]
val xs3 = ListMonad.map(plusOne)(xs) (* [2,3,4] *)
val xs4 = ListMonad.flatMap(xs)(repeat) (* [1,1,1,2,2,2,3,3,3] *)``````

Thanks to inheritence, both `ListFunctor#map` as well as `ListMonad#flatMap` directly on the list monad instance.