# 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

[ Top | Parent | Contents | Index | Root ]

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