lib/mlton/basic/linked-list.sig

   1 (* Copyright (C) 2009 Matthew Fluet.
   2  * Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh
   3  *    Jagannathan, and Stephen Weeks.
   4  *
   5  * MLton is released under a BSD-style license.
   6  * See the file MLton-LICENSE for details.
   7  *)
   8
   9 signature LINKED_LIST =
  10    sig
  11       type 'a t
  12
  13       val empty: unit -> 'a t
  14       val fold: 'a t * 'b * ('a * 'b -> 'b) -> 'b
  15       val fromList: 'a list -> 'a t
  16       val layout: ('a -> Layout.t) -> 'a t -> Layout.t
  17       (* in-place reverse *)
  18       val reverse: 'a t -> unit
  19       (* splice (l, r) extends l with r *)
  20       val splice: 'a t * 'a t -> unit
  21       val toList: 'a t -> 'a list
  22       val unfold: 'a * ('a -> ('b * 'a) option) -> 'b t
  23       val unfoldi: int * 'a * (int * 'a -> 'b * 'a) -> 'b t
  24       val unfoldr: 'a * ('a -> ('b * 'a) option) -> 'b t
  25       val unfoldri: int * 'a * (int * 'a -> 'b * 'a) -> 'b t
  26    end
  27
  28 functor TestLinkedList (S: LINKED_LIST): sig end =
  29 struct
  30
  31 open S
  32
  33 val _ =
  34    Assert.assert
  35    ("TestLinkedList", fn () =>
  36     List.forall ([[],
  37                   [1],
  38                   [1, 2],
  39                   [1, 2, 3]],
  40                  fn l =>
  41                  l = toList (fromList l)
  42                  andalso rev l = toList (let
  43                                             val l' = fromList l
  44                                             val _ = reverse l'
  45                                          in
  46                                             l'
  47                                          end)
  48                  andalso
  49                  let
  50                     val l' = fromList l
  51                     val l'' = fromList l
  52                     val _ = splice (l', l'')
  53                  in
  54                     l @ l = toList l'
  55                  end))
  56
  57 end