Standard ML functors and list combinators

listekomb.sml

(* Først defineres en signatur for lister.  Den indeholder nogle
 * af de mest elementære operationer, man kan lave på lister. *)
signature LISTE =
sig
  type 'a liste
  val null : 'a liste -> bool
  val empty : 'a liste
  val cons : 'a * 'a liste -> 'a liste
  val hd : 'a liste -> 'a
  val tl : 'a liste -> 'a liste
end
 
(* Her defineres en struktur for almindelige lister, svarende til
 * de indbyggede lister i Standard ML. *)
structure AlmListe : LISTE =
struct
  type 'a liste = 'a list
  val null = List.null
  val empty = nil (* [] *)
  val cons = op::
  val hd = List.hd
  val tl = List.tl
end
 
(* Her defineres en struktur for "dovne" lister, der er kendetegnet
 * ved at halen, i stedet for at være en fuldt ekspanderet liste,
 * er en funktion som kan evalueres. *)
structure DovenListe : LISTE =
struct
  datatype 'a liste = Nil
		    | Cons of 'a * (unit -> 'a liste)
  val empty = Nil
  fun null Nil = true
    | null _ = false
  fun cons (x, xs) = Cons (x, fn () => xs)
  fun hd Nil = raise Empty
    | hd (Cons (x, _)) = x
  fun tl Nil = raise Empty
    | tl (Cons (_, f)) = f ()
end
 
(* Man kunne lave andre slags lister som fungerer anderledes indvendigt,
 * men som har præcis samme grænseflade (signatur). I stedet er nedenfor
 * en række funktioner som kunne være nyttige at udføre på alle mulige
 * slags lister. *)
signature LISTEKOMB =
sig
  type 'a liste
 
  val length : 'a liste -> int
  val map : ('a -> 'b) -> 'a liste -> 'b liste
  val foldl : ('a * 'b -> 'b) -> 'b -> 'a liste -> 'b
  val append : 'a liste * 'a liste -> 'a liste
  val concat : 'a liste liste -> 'a liste
end
 
(* Hvis disse funktioner skal være tilgængelige for almindelige lister,
 * dovne lister og alle mulige andre slags lister, kan man lave dem i
 * strukturer kaldet AlmListeKomb, DovenListeKomb osv.: *)
structure AlmListeKomb : LISTEKOMB =
struct
  (* LISTEKOMB kræver en polymorf type, som lånes fra AlmListe *)
  type 'a liste = 'a AlmListe.liste

  fun length xs =
      if AlmListe.null xs then 0
      else 1 + length (AlmListe.tl xs)

  fun map f xs =
      if AlmListe.null xs then AlmListe.empty
      else AlmListe.cons(f (AlmListe.hd xs), map f (AlmListe.tl xs))

  fun foldl f e xs =
      if AlmListe.null xs then e
      else foldl f (f (AlmListe.hd xs, e)) (AlmListe.tl xs)
 
  fun append (xs, ys) =
      if AlmListe.null xs then ys
      else AlmListe.cons (AlmListe.hd xs, append (AlmListe.tl xs, ys))
 
  fun concat xs =
      if AlmListe.null xs then AlmListe.empty
      else append (AlmListe.hd xs, concat (AlmListe.tl xs))
end

(* Og lad os lave udkastet til DovenListeKomb, så vi også har et bibliotek
 * af funktioner som kan bruges på "dovne" lister. Men lad os gøre noget
 * smart... *)
structure DovenListeKomb : LISTEKOMB =
struct
  (* Smart: Lad os gøre alle DovenListe-funktionerne tilgængelige direkte
   * i dette virkefelt, så vi slipper for at skrive DovenListe foran alt. *)
  open DovenListe

  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))
end

(* Men nu er den eneste forskel der behøver at være mellem AlmListeKomb og
 * DovenListeKomb én linje: open AlmListe / open DovenListe, da de har samme
 * signatur og derfor indeholder samme funktioner med samme typer. Hvis
 * strukturer var ligesom funktioner, ville det være smart at lave en
 * højereordensfunktion som bare tager strukturen som argument X og så åbner X.
 *
 * En funktor kan ses som en højereordensstruktur: Noget som tager en struktur
 * som argument og returnerer en ny struktur baseret på den.
 *
 * Derfor laves en funktor i stedet. Funktoren tager en struktur, X, som
 * argument. Denne struktur er en parameter til funktoren, så den er partielt
 * anvendt, lidt ligesom funktioner kan være det. *)
functor ListeKomb (X : LISTE) : LISTEKOMB =
struct
  (* Fordi signaturen LISTEKOMB nævner typen 'a liste, skal denne type
   * defineres. Pointen er her at benytte 'a liste fra EnListe. Fordi
   * typen ligger inde i strukturen sådan at strukturens funktioner kan
   * anvendes, skal typen præfikses med 'X.', men fordi typen tager en
   * parameter, skal denne parameter nævnes først. *)
  type 'a liste = 'a X.liste
 
  (* For at forsimple udtrykkene nedenfor, åbnes listen som er givet. *)
  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))
end
 
(* Nu kan strukturer for listekombinatorer som virker særligt på almindelige og
 * dovne lister løses trivielt ved at anvende funktoren på de strukturer som
 * indeholder de typer og funktioner/værdier, som er nødvendige for
 * kombinatorerne. *)

structure AlmListeKomb = ListeKomb (AlmListe)
 
structure DovenListeKomb = ListeKomb (DovenListe)