# 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))

```