title: Standard ML functor examples
body: <p>Functors in Standard ML are related to the module system and can generate structures based on other structures. An example of a functor generating list combinators for various types of lists is given below, but this example has a problem:</p>
  
  <p>The various types of lists all have advantages -- for example, lazy lists can be infinitely long, and concantenation lists have a O(1) concat operator. But when all of these list types conform to the same signature, the functor can only use their general properties.</p>
  
  <p>My question is therefore: What is a good example of when functors are useful and the various generated structures don't lose their special abilities?</p>
  
  <pre><code>signature MYLIST =
  sig
    type 'a t
    val null : 'a t -&gt; bool
    val empty : 'a t
    val cons : 'a * 'a t -&gt; 'a t
    val hd : 'a t -&gt; 'a
    val tl : 'a t -&gt; 'a t
  end
  
  structure RegularList : MYLIST =
  struct
    type 'a t = 'a list
    val null = List.null
    val empty = []
    val cons = op::
    val hd = List.hd
    val tl = List.tl
  end
  
  structure LazyList : MYLIST =
  struct
    datatype 'a t = Nil | Cons of 'a * (unit -&gt; 'a t)
     val empty = Nil
     fun null Nil = true
      | null _ = false
     fun cons (x, xs) = Cons (x, fn () =&gt; xs)
     fun hd Nil = raise Empty
      | hd (Cons (x, _)) = x
     fun tl Nil = raise Empty
      | tl (Cons (_, f)) = f ()
  end
  
  structure ConcatList : MYLIST =
  struct
    datatype 'a t = Nil | Singleton of 'a | Concat of 'a t * 'a t
    val empty = Nil
    fun null Nil = true
      | null (Singleton _) = false
      | null (Concat (xs, ys)) = null xs andalso null ys
    fun cons (x, xs) = Concat (Singleton x, xs)
    fun hd Nil = raise Empty
      | hd (Singleton x) = x
      | hd (Concat (xs, ys)) = hd xs
    fun tl Nil = raise Empty
      | tl (Singleton x) = Nil
      | tl (Concat (xs, ys)) = (* exercise *)
  end
  
  signature MYLISTCOMB =
  sig
    type 'a t
    val length : 'a liste -&gt; int
    val map : ('a -&gt; 'b) -&gt; 'a liste -&gt; 'b liste
    val foldl : ('a * 'b -&gt; 'b) -&gt; 'b -&gt; 'a liste -&gt; 'b
    val append : 'a liste * 'a liste -&gt; 'a liste
    val concat : 'a liste liste -&gt; 'a liste
    val sort : ('a * 'a -&gt; order) -&gt; 'a t -&gt; 'a t
  end
  
  functor ListComb (X : MYLIST) : MYLISTCOMB =
  struct
    type 'a t = 'a X.t
    open X
  
    fun length xs =
        if null xs then 0
        else 1 + length (tl xs)
  
    fun map f xs =
        if null xs then empty
        else cons(f (hd xs), map f (tl xs))
  
    fun foldl f e xs =
        if null xs then e
        else foldl f (f (hd xs, e)) (tl xs)
  
    fun append (xs, ys) =
        if null xs then ys
        else cons (hd xs, append (tl xs, ys))
  
    fun concat xs =
        if null xs then empty
        else append (hd xs, concat (tl xs))
  
    fun sort cmp xs = (* exercise *)
  end
  
  structure RegularListComb = ListComb (RegularList)
  structure LazyListComb = ListComb (LazyList)
  structure ConcatListComb = ListComb (ConcatList)
  </code></pre>