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