Module Prelude.Stack

See STACK.

type 'a t = private 'a list

The type of stacks.

val compare : 'a t -> 'a t -> int

compare is the version of compare for t's.

val empty : 'a t

The empty stack.

val size : 'a t -> int

(size s) is the number of items on the stack s.

val push : 'a -> 'a t -> 'a t

(push x s) returns a new stack with x on top of it.

val dup : 'a t -> 'a t

dup is Forth's DUP i.e. it pushes a copy of the top item of s onto s.

val top : 'a t -> 'a option

(top s) is the top item on stack s.

val drop : 'a t -> 'a t

drop is (pop $ snd): it throws away the top item on s.

Invariant: (push x s |> drop) = s

val pop : 'a t -> 'a option * 'a t

(pop s) is (top s, drop s)

Invariants:

  • (pop empty) = (None, empty)
  • (push x s |> pop) = (Some x,s)
val swap : 'a t -> 'a t

swap is Forth's SWAP.

Applying swap to the empty list or to a singleton list has no effect.

Invariants:

  • (push x empty |> swap |> pop) = (None, empty)
  • (push x s |> push y |> swap |> pop) = (Some x, push y s)
val map : ('a -> 'b) -> 'a t -> 'b t

(map f t) maps f across each element in the stack t.

val fold : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

(fold f init t) folds f across the stack t with init as the initial accumulator.

val of_list : 'a list -> 'a t

(of_list (x::[])) = (push x empty)

val to_list : 'a t -> 'a list

(push 1 empty |> push 2 |> to_list) = [2;1]

val random : ?size:(unit -> int) -> (unit -> 'a) -> unit -> 'a t

(random ?size r ()) is a random stack of size (size ()) (default: < 100), and each element is given by (r ()).