Standard ML functors and list combinators

listekomb.sml

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

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

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

(* structure SjovListe : LISTE = *)
(* struct *)
(*   ... *)
(* end *)

signature LISTEKOMB =
sig
  include LISTE
  val map : ('a -> 'b) -> 'a liste -> 'b liste
  val foldl : ('a * 'b -> 'b) -> 'b -> 'a liste -> 'b
end

(* (* Det her er unødvendigt: *)
structure SjovListeKomb : LISTEKOMB =
struct
  open SjovListe

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

  fun foldl ...
end
*)

functor ListeKomb (EnListe : LISTE) : LISTEKOMB =
struct
  open EnListe

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

structure AlmListeKomb = ListeKomb (AlmListe)

structure DovenListeKomb = ListeKomb (DovenListe)

(* structure SjovListeKomb = ListeKomb (SjovListe) *)