SML/NJ Library Manual

The Fifo structure

Synopsis

signature FIFO
structure Fifo : FIFO


The Fifo structure provides an applicative implementation of queues, in one of the greater abuses of notation.

As the implementation uses a pair of lists, the amortized cost for calling enqueue, dequeue or head is constant time.

Interface

type 'a fifo
exception Dequeue
val empty : 'a fifo
val isEmpty : 'a fifo -> bool
val enqueue : ('a fifo * 'a) -> 'a fifo
val dequeue : 'a fifo -> ('a fifo * 'a)
val delete : ('a fifo * ('a -> bool)) -> 'a fifo
val head : 'a fifo -> 'a
val peek : 'a fifo -> 'a option
val length : 'a fifo -> int
val contents : 'a fifo -> 'a list
val app : ('a -> unit) -> 'a fifo -> unit
val map : ('a -> 'b) -> 'a fifo -> 'b fifo
val foldl : (('a * 'b) -> 'b) -> 'b -> 'a fifo -> 'b
val foldr : (('a * 'b) -> 'b) -> 'b -> 'a fifo -> 'b


Description

type 'a fifo

exception Dequeue

empty

is an empty queue.

isEmpty fi

returns true if fi is empty.

enqueue (fi, a)

creates a new queue by appending a to the tail of fi.

dequeue fi

returns the head of fi plus the remainder of fi after the head is removed. Raises the exception Dequeue if fi is empty.

delete (fi, f)

creates a new queue by deleting from fi all elements satisfying the predicate f. The order of the remaining elements is preserved.

head fi

returns the head of fi, without changing fi. Raises the exception Dequeue if fi is empty.

peek fi

returns the head of fi if it exists; otherwise, returns NONE.

length fi

returns the number of elements in fi. At present, this is a linear time operation.

contents fi

returns the elements in fi in queue order. This is a linear time operation.

app f fi

applies the function f to the elements in fi in queue order. This is equivalent to:

            List.app f (contents fi)
          

map f fi

creates a new queue by mapping the elements in fi by f. This is equivalent to:

            List.foldl (fn (v,q) => enqueue(q,v)) empty (List.map f (contents fi))
          

foldl f a fi

folds the elements of the queue from the head to the tail. This is equivalent to:

            List.foldl f a (contents fi))
          

foldr f a fi

folds the elements of the queue from the tail to the head. This is equivalent to:

            List.foldr f a (contents fi))
          

See Also

Queue

Last Modified May 14, 1998
Comments to John Reppy
Copyright © 1998 Bell Labs, Lucent Technologies