Monoids - SML

1. Introduction
2. Examples
- 2.1. Built-in structures

1. Introduction

A monoid can be seen as a generalization of lists or strings. It's a typeclass (see Haskell's Data.Monoid), so it is implemented in Standard ML by a signature which is transparently ascribed to a structure (if at all):

signature MONOID = sig
  type 'a t;
  val empty : 'a t;
  val append : 'a t -> 'a t -> 'a t;
  val concat : 'a t list -> 'a t;
  (* fun concat xs = List.foldr append empty xs *)
end;

The laws it needs to satisfy:

Identity laws: append x empty = x and append empty x = x
Associativity: append (append x y) z = append x (append y z)
Concatenation: concat = foldr append empty

…and that's it.

Care must be taken with the signature, since Haskell is more flexible in its ability to allow quantifiers. If we want to be faithful to Haskell, we should have our signature's first line be type t; without any type variable. But then we couldn't implement a ListMonoid, since the list type constructor requires 1 type variable whereas type t has zero type variables (and \(0\neq1\) which causes Standard ML to believe this is not a valid type definition).

On the other hand, if we take type 'a t; (as we did) in the first line of the signature MONOID, then we have a phantom type when dealing with strings.

Given the choice between making lists not monoids or phantom types for string monoids, the latter seems less bad (but not ideal).

2. Examples

2.1. Built-in structures

We can "hack" the List and String structures to make them satisfy the monoid signature.

structure List = struct
  open List;
  type 'a t = 'a list;
  val empty = nil;
  fun append xs ys = xs @ ys;
end;

structure String = struct
  open String;
  type 'a t = string;
  val empty : 'a t = "";
  fun append (xs : 'a t) (ys : 'a t) : 'a t = xs ^ ys;
end;

This is obviously not as elegant as what could be found in Haskell.

Monoids - SML

Table of Contents

1. Introduction

2. Examples

2.1. Built-in structures