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.