Module type Prelude.STACK

Purely functional stacks.

Basically, a set of functions that treat lists as stacks, and a private type to enhance type safety.

The hd of the list is the top of the stack.

Conversion between lists and stacks is essentially free, and you can coerce stacks to lists for pattern matching:

match ((empty |> push 1) :> int list) with [] -> ...
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 ()).