lib/mlton/basic/list.sig

   1 (* Copyright (C) 2009,2017 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 LIST =
  10    sig
  11       type 'a t = 'a list
  12
  13       val allButLast: 'a t -> 'a t
  14       val append: 'a t * 'a t -> 'a t
  15       (* appendMap (l1, f, l2) = append (map (l1, f), l2) *)
  16       val appendMap: 'a t * ('a -> 'b) * 'b t -> 'b t
  17       (* appendRev (l1, l2) = append (rev l1, l2) *)
  18       val appendRev: 'a t * 'a t -> 'a t
  19       val compare: 'a t * 'a t * ('a * 'a -> order) -> order
  20       (* concat [[1, 2], [3, 4, 5], [6]] = [1, 2, 3, 4, 5, 6] *)
  21       val concat: 'a t t -> 'a t
  22       (* concatMap = concat o map *)
  23       val concatMap: 'a t * ('a -> 'b t) -> 'b t
  24       (* concatRev = concat o rev *)
  25       val concatRev: 'a t t -> 'a t
  26       val cons: 'a * 'a t -> 'a t
  27       val contains: 'a t * 'a * ('a * 'a -> bool) -> bool
  28       (*   cross [[1, 2, 3], [4, 5], [6, 7]] =
  29        * [[1, 4, 6], [1, 4, 7], [1, 5, 6], [1, 5, 7],
  30        *  [2, 4, 6], [2, 4, 7], [2, 5, 6], [2, 5, 7],
  31        *  [3, 4, 6], [3, 4, 7], [3, 5, 6], [3, 5, 7]]
  32        *)
  33       val cross: 'a t t -> 'a t t
  34       val dropPrefix: 'a t * int -> 'a t
  35       val dropSuffix: 'a t * int -> 'a t
  36       (* duplicate (3, f) = [f (), f (), f ()] *)
  37       val duplicate: int * (unit -> 'a) -> 'a t
  38       (* Extract each element paired with the elements before it
  39        * and after it in the same order as in the list.
  40        *)
  41 (*      val each: 'a t -> ('a t * 'a * 'a t) t *)
  42       val equals: 'a t * 'b t * ('a * 'b -> bool) -> bool
  43       val equalsAsSet: 'a t * 'a t * ('a * 'a -> bool) -> bool
  44       (* Group according to equivalence relation. *)
  45       val equivalence: 'a t * ('a * 'a -> bool) -> 'a t t
  46       val exists: 'a t * ('a -> bool) -> bool
  47       val first: 'a t -> 'a
  48       val firstN: 'a t * int -> 'a t
  49       val fold: 'a t * 'b * ('a * 'b -> 'b) -> 'b
  50       val fold2: 'a t * 'b t * 'c * ('a * 'b * 'c -> 'c) -> 'c
  51       val fold3: 'a t * 'b t * 'c t * 'd * ('a * 'b * 'c * 'd -> 'd) -> 'd
  52       val foldi: 'a t * 'b * (int * 'a * 'b -> 'b) -> 'b
  53       val foldr: 'a t * 'b * ('a * 'b -> 'b) -> 'b
  54       val foldr2: 'a t * 'b t * 'c * ('a * 'b * 'c -> 'c) -> 'c
  55       val forall: 'a t * ('a -> bool) -> bool
  56       val forall2: 'a t * 'b t * ('a * 'b -> bool) -> bool
  57       val foralli: 'a t * (int * 'a -> bool) -> bool
  58       val foreach: 'a t * ('a -> unit) -> unit
  59       val foreach2: 'a t * 'b t * ('a * 'b -> unit) -> unit
  60 (*      val foreach3: 'a t * 'b t * 'c t * ('a * 'b * 'c -> unit) -> unit *)
  61       val foreachi: 'a t * (int * 'a -> unit) -> unit
  62       val index: 'a t * ('a -> bool) -> int option
  63       (* Insert an element in a list sorted in increasing order.
  64        * Return the original list if the the element is already there.
  65        *)
  66       val insert: 'a t * 'a * ('a * 'a -> bool) -> 'a t
  67       val insertionSort: 'a t * ('a * 'a -> bool) -> 'a t
  68       val isEmpty: 'a t -> bool
  69       val isPrefix: 'a t * 'a t * ('a * 'a -> bool) -> bool
  70       val keepAll: 'a t * ('a -> bool) -> 'a t
  71       val keepAllMap: 'a t * ('a -> 'b option) -> 'b t
  72       val last: 'a t -> 'a
  73       val layout: ('a -> Layout.t) -> 'a t -> Layout.t
  74       (* Specify a string to separate the elements *)
  75 (*      val layoutSep: string * ('a -> Layout.t) -> 'a t -> Layout.t *)
  76       val length: 'a t -> int
  77       val map: 'a t * ('a -> 'b) -> 'b t
  78       val mapi: 'a t * (int * 'a -> 'b) -> 'b t
  79       val map2: 'a t * 'b t * ('a * 'b -> 'c) -> 'c t
  80       val map3: 'a t * 'b t * 'c t * ('a * 'b * 'c -> 'd) -> 'd t
  81 (*      val map4: 'a t * 'b t * 'c t * 'd t * ('a * 'b * 'c * 'd -> 'e) -> 'e t *)
  82       val new: int * 'a -> 'a t
  83       val nth: 'a t * int -> 'a
  84       val nthTail: 'a t * int -> 'a t
  85 (*       val ordered :
  86  *       {< : 'a * 'a -> bool}
  87  *       -> {insert: 'a t * 'a -> 'a t,
  88  *           insertionSort: 'a t  -> 'a t,
  89  *           median: 'a t -> 'a,
  90  *           orderStatistic: 'a t * int -> 'a,
  91  *           partition: 'a t * 'a -> 'a t * 'a t,
  92  *           max: 'a t -> 'a,
  93  *           min: 'a t -> 'a,
  94  *           largest: 'a t * int -> 'a t,
  95  *           smallest: 'a t * int -> 'a t}
  96  *)
  97       (* partition ([1, 2, 3, 4], isOdd) = {no = [4, 2], yes = [3, 1]} *)
  98       val partition: 'a t * ('a -> bool) -> {no: 'a t, yes: 'a t}
  99       val peek: 'a t * ('a -> bool) -> 'a option
 100       val peeki: 'a t * (int * 'a -> bool) -> (int * 'a) option
 101       val peekMap: 'a t * ('a -> 'b option) -> 'b option
 102       (* Removes first element if it exists.
 103        * Returns NONE if pred is false on everything.
 104        *)
 105 (*      val peekRemove: 'a t * ('a -> bool) -> ('a t * 'a) option *)
 106       val pop: 'a t ref -> 'a
 107       val power: 'a t -> 'a t t
 108 (*      val prefixes: 'a t -> 'a t t*)
 109       val push: 'a t ref * 'a -> unit
 110       (* Removes first element on which predicate is true.
 111        * Returns original list if predicate is false on every elt.
 112        *)
 113       val remove: 'a t * ('a -> bool) -> 'a t
 114       (* removeAll (l, f) removes all x in l such that f x and reverses order. *)
 115       val removeAll: 'a t * ('a -> bool) -> 'a t
 116       val removeCommonPrefix: 'a t * 'a t * ('a * 'a -> bool) -> 'a t * 'a t
 117       val removeDuplicates: 'a t * ('a * 'a -> bool) -> 'a t
 118       (* Error if predicate isn't true on some element. *)
 119       val removeFirst: 'a t * ('a -> bool) -> 'a t
 120       val removePrefix: 'a t * ('a -> bool) -> 'a t
 121       val rev: 'a t -> 'a t
 122       (* The "rev" versions of functions are there for efficiency, when it is
 123        * easier to fold over the input and accumulate the result in reverse.
 124        *)
 125       val revMap: 'a t * ('a -> 'b) -> 'b t
 126       val revKeepAll: 'a t * ('a -> bool) -> 'a t
 127       val revKeepAllMap: 'a t * ('a -> 'b option) -> 'b t
 128       val revRemoveAll: 'a t * ('a -> bool) -> 'a t
 129       val separate: 'a t * 'a -> 'a t
 130       val set: {equals: 'a * 'a -> bool,
 131                 layout: 'a -> Layout.t}
 132          -> {empty: 'a t,
 133              singleton: 'a -> 'a t,
 134              size: 'a t -> int,
 135              equals: 'a t * 'a t -> bool,
 136              <= : 'a t * 'a t -> bool,
 137              >= : 'a t * 'a t -> bool,
 138              < : 'a t * 'a t -> bool,
 139              > : 'a t * 'a t -> bool,
 140              + : 'a t * 'a t -> 'a t,
 141              - : 'a t * 'a t -> 'a t,
 142              intersect: 'a t * 'a t -> 'a t,
 143              unions: 'a t t -> 'a t,
 144              add: 'a t * 'a -> 'a t,
 145              remove: 'a t * 'a -> 'a t,
 146              contains: 'a t * 'a -> bool,
 147              areDisjoint: 'a t * 'a t -> bool,
 148              subset: 'a t * ('a -> bool) -> 'a t,
 149              subsetSize: 'a t * ('a -> bool) -> int,
 150              replace: 'a t * ('a -> 'a option) -> 'a t,
 151              map: 'a t * ('a -> 'a) -> 'a t,
 152              layout: 'a t -> Layout.t}
 153       val snoc: 'a t * 'a -> 'a t
 154 (*      val splitAtMost: 'a t * int -> ('a t * 'a t) option *)
 155       val splitAt: 'a t * int -> 'a t * 'a t
 156       val splitLast: 'a t -> 'a t * 'a
 157       val splitPrefix: 'a t * ('a -> bool) -> 'a t * 'a t
 158 (*      val suffixes: 'a t -> 'a t t *)
 159       (* subsets (l, n) = subsets of exactly size n *)
 160       val subsets: 'a t * int -> 'a t t
 161       val tabulate: int * (int -> 'a) -> 'a t
 162 (*      val tail: 'a t -> 'a t *)
 163       val toString: ('a -> string) -> 'a t -> string
 164       val unfold: 'a * ('a -> ('b * 'a) option) -> 'b t
 165       val unfoldi: int * 'a * (int * 'a -> 'b * 'a) -> 'b t
 166       val unfoldr: 'a * ('a -> ('b * 'a) option) -> 'b t
 167       val unfoldri: int * 'a * (int * 'a -> 'b * 'a) -> 'b t
 168       val union: 'a t * 'a t * ('a * 'a -> bool) -> 'a t
 169       val unzip: ('a * 'b) t -> 'a t * 'b t
 170 (*      val unzip3: ('a * 'b * 'c) t -> 'a t * 'b t * 'c t *)
 171       val zip: 'a t * 'b t -> ('a * 'b) t
 172 (*      val zip3: 'a t * 'b t * 'c t -> ('a * 'b * 'c) t *)
 173    end
 174
 175
 176 functor TestList (S: LIST): sig end =
 177 struct
 178
 179 val _ = print "TestList\n"
 180
 181 open S
 182
 183 val _ =
 184    Assert.assert
 185    ("TestList", fn () =>
 186     SOME true = peekMap ([1, 2, 3], fn x => if x = 2 then SOME true else NONE)
 187     andalso ([2], [3]) = removeCommonPrefix ([1, 2], [1, 3], op =)
 188     andalso [2, 4, 6] = keepAll ([1, 2, 3, 4, 5, 6], fn x => 0 = x mod 2))
 189
 190 end