Notes on Standard ML

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.

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] *)

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.

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

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.

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.

Ad Hoc Polymorphism in SML