199 lines
8.0 KiB
Standard ML
199 lines
8.0 KiB
Standard ML
|
|
|
|
|
|
(*--------------------------------------------------------------------------*)
|
|
(* Structure: UtilList *)
|
|
(* *)
|
|
(* Depends on: *)
|
|
(* *)
|
|
(* Exceptions raised by functions in this structure: *)
|
|
(* member : none *)
|
|
(* findAndDelete : none *)
|
|
(*--------------------------------------------------------------------------*)
|
|
signature UtilList =
|
|
sig
|
|
val split : ('a -> bool) -> 'a list -> 'a list list
|
|
val member : ''a -> ''a list -> bool
|
|
val mapAllPairs : ('a * 'b -> 'c) -> 'a list * 'b list -> 'c list
|
|
val findAndMap : ('a -> 'b option) -> 'a list -> 'b option
|
|
val findAndDelete : ('a -> bool) -> 'a list -> ('a option * 'a list)
|
|
|
|
val sort : ('a * 'a -> order) -> 'a list -> 'a list
|
|
val merge : ('a * 'a -> order) -> 'a list * 'a list -> 'a list
|
|
val diff : ('a * 'a -> order) -> 'a list * 'a list -> 'a list
|
|
val cap : ('a * 'a -> order) -> 'a list * 'a list -> 'a list
|
|
val sub : ('a * 'a -> order) -> 'a list * 'a list -> bool
|
|
val insert : ('a * 'a -> order) -> 'a * 'a list -> 'a list
|
|
val delete : ('a * 'a -> order) -> 'a * 'a list -> 'a list
|
|
val elem : ('a * 'a -> order) -> 'a * 'a list -> bool
|
|
end
|
|
|
|
structure UtilList : UtilList =
|
|
struct
|
|
(*--------------------------------------------------------------------*)
|
|
(* split a list into a list of lists at each element fullfilling p. *)
|
|
(*--------------------------------------------------------------------*)
|
|
fun split p l =
|
|
let val (one,ls) = foldr
|
|
(fn (a,(curr,ls)) => if p a then (nil,curr::ls) else (a::curr,ls))
|
|
(nil,nil) l
|
|
in one::ls
|
|
end
|
|
|
|
(*--------------------------------------------------------------------*)
|
|
(* is x a member of l? *)
|
|
(*--------------------------------------------------------------------*)
|
|
fun member x l = List.exists (fn y => x=y) l
|
|
|
|
(*--------------------------------------------------------------------*)
|
|
(* for [a1,...,an] and [b1,...,bk], generate *)
|
|
(* [f(a1,b1),f(a1,b2),...,f(an,bk-1),f(an,bk)]. *)
|
|
(*--------------------------------------------------------------------*)
|
|
fun mapAllPairs f (ass,bs) =
|
|
foldr
|
|
(fn (a,cs) => foldr (fn (b,cs) => f(a,b)::cs) cs bs)
|
|
nil ass
|
|
|
|
(*--------------------------------------------------------------------*)
|
|
(* find the first element x of l such that f x = SOME y, and return *)
|
|
(* f x. If there is no such x, return NONE. *)
|
|
(*--------------------------------------------------------------------*)
|
|
fun findAndMap _ nil = NONE
|
|
| findAndMap f (x::xs) = case f x of NONE => findAndMap f xs | y => y
|
|
|
|
(*--------------------------------------------------------------------*)
|
|
(* find the first element x of l such that f x = true, delete it from *)
|
|
(* l, and return SOME x with the modified list. If there is no such x *)
|
|
(* return (NONE,l). *)
|
|
(*--------------------------------------------------------------------*)
|
|
fun findAndDelete _ nil = (NONE,nil)
|
|
| findAndDelete f (x::xs) =
|
|
if f x then (SOME x,xs)
|
|
else let val (y,ys) = findAndDelete f xs in (y,x::ys) end
|
|
|
|
(*--------------------------------------------------------------------*)
|
|
(* given a function that compares elements, merge two sorted lists. *)
|
|
(*--------------------------------------------------------------------*)
|
|
fun merge comp (l1,l2) =
|
|
let
|
|
fun go (nil,l) = l
|
|
| go (l,nil) = l
|
|
| go (l1 as (x1::r1),l2 as (x2::r2)) =
|
|
case comp(x1,x2)
|
|
of LESS => x1::go(r1,l2)
|
|
| EQUAL => go(l1,r2)
|
|
| GREATER => x2::go(l1,r2)
|
|
in go(l1,l2)
|
|
end
|
|
|
|
(*--------------------------------------------------------------------*)
|
|
(* given a comparing function, compute the intersection of two *)
|
|
(* ordered lists. *)
|
|
(*--------------------------------------------------------------------*)
|
|
fun cap comp (l1,l2) =
|
|
let
|
|
fun go (nil,l) = nil
|
|
| go (l,nil) = nil
|
|
| go (l1 as (x1::r1),l2 as (x2::r2)) =
|
|
case comp(x1,x2)
|
|
of LESS => go(r1,l2)
|
|
| EQUAL => x1::go(r1,r2)
|
|
| GREATER => go(l1,r2)
|
|
in go(l1,l2)
|
|
end
|
|
|
|
(*--------------------------------------------------------------------*)
|
|
(* given a comparing function, compute the difference of two *)
|
|
(* ordered lists. *)
|
|
(*--------------------------------------------------------------------*)
|
|
fun diff comp (l1,l2) =
|
|
let
|
|
fun go (nil,l) = nil
|
|
| go (l,nil) = l
|
|
| go (l1 as (x1::r1),l2 as (x2::r2)) =
|
|
case comp(x1,x2)
|
|
of LESS => x1::go(r1,l2)
|
|
| EQUAL => go(r1,r2)
|
|
| GREATER => go(l1,r2)
|
|
in go(l1,l2)
|
|
end
|
|
|
|
(*--------------------------------------------------------------------*)
|
|
(* given a comparing function, find out whether an ordered list is *)
|
|
(* contained in an other ordered list. *)
|
|
(*--------------------------------------------------------------------*)
|
|
fun sub comp (l1,l2) =
|
|
let
|
|
fun go (nil,l) = true
|
|
| go (l,nil) = false
|
|
| go (l1 as (x1::r1),l2 as (x2::r2)) =
|
|
case comp(x1,x2)
|
|
of LESS => false
|
|
| EQUAL => go(r1,r2)
|
|
| GREATER => go(l1,r2)
|
|
in go(l1,l2)
|
|
end
|
|
|
|
(*--------------------------------------------------------------------*)
|
|
(* given a function that compares elements, insert an element into an *)
|
|
(* ordered list. *)
|
|
(*--------------------------------------------------------------------*)
|
|
fun insert comp (x,l) =
|
|
let
|
|
fun go nil = [x]
|
|
| go (l as y::ys) =
|
|
case comp(x,y)
|
|
of LESS => x::l
|
|
| EQUAL => l
|
|
| GREATER => y::go ys
|
|
in go l
|
|
end
|
|
|
|
(*--------------------------------------------------------------------*)
|
|
(* given a function that compares elements, delete an element from *)
|
|
(* an ordered list. *)
|
|
(*--------------------------------------------------------------------*)
|
|
fun delete comp (x,l) =
|
|
let
|
|
fun go nil = [x]
|
|
| go (l as y::ys) =
|
|
case comp(x,y)
|
|
of LESS => l
|
|
| EQUAL => ys
|
|
| GREATER => y::go ys
|
|
in go l
|
|
end
|
|
|
|
(*--------------------------------------------------------------------*)
|
|
(* given a function that compares elements, insert an element into an *)
|
|
(* ordered list. *)
|
|
(*--------------------------------------------------------------------*)
|
|
fun elem comp (x,l) =
|
|
let
|
|
fun go nil = false
|
|
| go (l as y::ys) =
|
|
case comp(x,y)
|
|
of LESS => false
|
|
| EQUAL => true
|
|
| GREATER => go ys
|
|
in go l
|
|
end
|
|
|
|
(*--------------------------------------------------------------------*)
|
|
(* merge-sort a list of elements comparable with the function in the *)
|
|
(* 1st argument. Preserve duplicate elements. *)
|
|
(*--------------------------------------------------------------------*)
|
|
fun sort _ nil = nil
|
|
| sort comp l =
|
|
let fun mergeOne (x::y::l) = merge comp (x,y)::mergeOne l
|
|
| mergeOne l = l
|
|
fun mergeAll [l] = l
|
|
| mergeAll ls = mergeAll (mergeOne ls)
|
|
val singles = map (fn x => [x]) l
|
|
in
|
|
mergeAll singles
|
|
end
|
|
|
|
end
|
|
|