Bag structure

Up to index

The Bag structure provides operations on bags (also known as multisets), which are unordered collections that may contain duplicate elements. Unlike lists, bags do not maintain element order; unlike sets, bags track multiplicity.

Synopsis

type 'a bag

val nil : 'a bag
val null : 'a bag -> bool
val fromList : 'a list -> 'a bag
val toList : 'a bag -> 'a list
val length : 'a bag -> int
val @ : 'a bag * 'a bag -> 'a bag
val hd : 'a bag -> 'a
val tl : 'a bag -> 'a bag
val getItem : 'a bag -> ('a * 'a bag) option
val take : 'a bag * int -> 'a bag
val drop : 'a bag * int -> 'a bag
val concat : 'a bag list -> 'a bag
val app : ('a -> unit) -> 'a bag -> unit
val map : ('a -> 'b) -> 'a bag -> 'b bag
val mapPartial : ('a -> 'b option) -> 'a bag -> 'b bag
val find : ('a -> bool) -> 'a bag -> 'a option
val filter : ('a -> bool) -> 'a bag -> 'a bag
val partition : ('a -> bool) -> 'a bag -> 'a bag * 'a bag
val fold : ('a * 'b -> 'b) -> 'b -> 'a bag -> 'b
val exists : ('a -> bool) -> 'a bag -> bool
val all : ('a -> bool) -> 'a bag -> bool
val tabulate : int * (int -> 'a) -> 'a bag
val nth : 'a bag * int -> 'a
val only : 'a bag -> 'a

type 'a bag

nil

nil is the empty bag.

null

null b (or b.null ()) returns true if the bag b is empty.

fromList

fromList l creates a new bag from l, whose length is length l and whose elements are the same as those of l. Raises Size if maxLen < n.

toList

toList b (or b.toList ()) creates a new bag from b, whose length is length b and whose elements are the same as those of b. Raises Size if maxLen < n.

length

length b (or b.length ()) returns the number of elements in the bag b.

@

@ (b1, b2) returns the bag that is the concatenation of b1 and b2.

hd

hd b (or b.hd ()) returns an arbitrary element of bag b. Raises Empty if b is nil.

tl

tl b (or b.tl ()) returns all but one arbitrary element of bag b. Raises Empty if b is nil.

getItem

getItem b (or b.getItem ()) returns NONE if the bag b is empty, and SOME (hd b, tl b) otherwise (applying hd and tl simultaneously so that they choose/remove the same arbitrary element).

take

take (b, i) (or b.take i) returns an arbitrary i elements of the bag b. Raises Subscript if i < 0 or i > length l. We have take(b, length b) = b.

drop

drop (b, i) (or b.drop i) returns what is left after dropping an arbitrary i elements of the bag b. Raises Subscript if i < 0 or i > length l.

We have drop(b, length b) = [].

concat

concat b returns the bag that is the concatenation of all the bags in b.

app

app f b applies f to the elements of b.

map

map f b applies f to each element of b, returning the bag of results. This is equivalent to:

fromList (List.map f (foldr (fn (a,l) => a::l) [] b))

mapPartial

mapPartial f b applies f to each element of b, returning a bag of results, with SOME stripped, where f was defined. f is not defined for an element of b if f applied to the element returns NONE. The above expression is equivalent to:

((map valOf) o (filter isSome) o (map f)) b

find

find f b applies f to each element x of the bag b, in arbitrary order, until f x evaluates to true. It returns SOME (x) if such an x exists; otherwise it returns NONE.

filter

filter f b applies f to each element x of b and returns the bag of those x for which f x evaluated to true.

partition

partition f b applies f to each element x of b, in arbitrary order, and returns a pair (pos, neg) where pos is the bag of those x for which f x evaluated to true, and neg is the bag of those for which f x evaluated to false.

fold

fold f init (bag [x1, x2, ..., xn]) returns f(xn, ... , f(x2, f(x1, init))...) (for some arbitrary reordering of the elements xi) or init if the bag is empty.

exists

exists f b applies f to each element x of the bag b, in arbitrary order, until f(x) evaluates to true; it returns true if such an x exists and false otherwise.

all

all f b applies f to each element x of the bag b, in arbitrary order, until f(x) evaluates to false; it returns false if such an x exists and true otherwise. It is equivalent to not(exists (not o f) b)).

tabulate

tabulate (n, f) returns a bag of length n equal to [f(0), f(1), ..., f(n-1)]. This is equivalent to the expression:

fromList (List.tabulate (n, f))

Raises Size if n < 0.

nth

nth (b, i) (or b.nth i) returns the ith element of the bag b, counting from 0. Raises Subscript if i < 0 or i >= length b. We have nth(b,0) = hd b, ignoring exceptions.

only

only b (or b.only ()) returns the only element of bag b. Raises Empty if b is empty, Size if b has more than one element.