The Util Library

## Overview

The Util Library provides a large collection of utility data structures and algorithms. It is the core library in the SML/NJ Library suite and dates back to the early 1990’s, where it was originally developed by Emden Gansner and John Reppy as part of the eXene X11 toolkit. Modules from this library are autoloaded into the SML/NJ interactive environment by default.

## Contents

`structure ANSITerm`

provides support for displaying stylized text using the ANSI escape codes.

`structure ArrayQSort`

Provides in situ sorting of polymorphic arrays using the quicksort algorithm.

`functor ArrayQSortFn`

Provides in situ sorting of monomorphic arrays using the quicksort algorithm.

`structure Atom`

provides hashed strings that have fast equality testing.

`structure Base64`

Provides support for Base-64 encoding/decoding as specified by RFC 4648.

`functor BinaryMapFn`

Provides a balanced-binary-tree implementation of the `ORD_MAP` signature parameterized over the key type.

`functor BinarySetFn`

Provides a balanced-binary-tree implementation of the `ORD_SET` signature parameterized over the element type.

`structure BitArray`

Provides mutable arrays of booleans represented by one bit per element.

`functor BSearchFn`

Provides binary search on sorted monomorphic arrays.

`structure CharMap`

Provides fast, read-only, maps from 8-bit characters to values.

`structure DynamicArray`

Provides dynamically sized polymorphic arrays.

`functor DynamicArrayFn`

Provides dynamically sized monomorphic arrays.

`structure Fifo`

Provides a functional queue data structure.

`structure FNVHash`

Provides an implementation of the Fowler-Noll-Vo hashing algorithm.

`structure Format`

Provides `printf`-style string formatting.

`structure FormatComb`

To be written

`structure GetOpt`

Provides command-line argument processing.

`functor GraphSCCFn`

Provides an algorithm for computing the strongly-connected components of a directed graph.

`functor Hash2TableFn`

Provides hash tables that are keyed by two different key types.

`signature HASH_KEY`

Defines an interface to a monomorphic type with an equality test and hashing function.

`functor HashSetFn`

Provides a hash-table-based implementation of imperative sets parameterized over a `Key` structure.

`structure HashString`

Provides hashing functions for strings and substrings.

`structure HashTable`

Provides an implementation of polymorphic hash tables.

`functor HashTableFn`

Provides a functor that implements the `MONO_HASH_TABLE` signature.

`signature INTERVAL_DOMAIN`

Defines a representation of an abstract ordered domain that is used as an argument to the `IntervalSetFn` functor.

`functor IntervalSetFn`

Provides sets over a discrete ordered domain, where the sets are represented by intervals.

`structure IOUtil`

Provides support for redirecting the standard input and output streams.

`functor KeywordFn`

Provides a simple way to support a table of keyword (or reserved) identifiers in a scanner.

`functor LeftPriorityQFn`

Provides a functional implementation of priority queues using leaftist heaps.

`structure LibBase`

Provides some common definitions that are shared across the SML/NJ Lbrary.

`structure ListFormat`

Provides some utility functions for converting lists into strings (and back).

`functor ListMapFn`

Provides a sorted-list implementation of the `ORD_MAP` signature parameterized over the key type.

`structure ListMergeSort`

Provides a merge-sort algorithm for lists.

`functor ListSetFn`

Provides a sorted-list implementation of the `ORD_SET` signature parameterized over the element type.

`structure ListXProd`

Provides list combinators for computing over the "Cartesian product" of two lists.

`functor MonoArrayFn`

Provides easy construction of new monomorphic array structures.

`signature MONO_HASH_TABLE`

Defines an interface to imperative hash tables with monomorphic keys.

`signature ORD_KEY`

Defines an interface to an abstract type of keys with a comparison function.

`signature ORD_MAP`

Defines an interface to finite maps over ordered keys.

`signature ORD_SET`

Defines an interface to finite sets of ordered elements.

`structure ParserComb`

Provides parser combinators over character readers.

`structure PathUtil`

Provides support for searching for files in the file system using a list of possible locations.

`structure PropList`

Provides a extensible, but type safe, implementation of property lists.

`structure Queue`

Provides an imperative queue data structure.

`structure Rand`

Provides a simple random number generator.

`structure Random`

Provides a more sophisticated random number generator.

`structure RealOrderStats`

To be written

`functor RedBlackMapFn`

Provides a red-black-tree implementation of the `ORD_MAP` signature parameterized over the key type.

`functor RedBlackSetFn`

Provides a red-black-tree implementation of the `ORD_SET` signature parameterized over the element type.

`structure Scan`

To be written

`functor SplayMapFn`

Provides a splay-tree implementation of the `ORD_MAP` signature parameterized over the key type.

`functor SplaySetFn`

Provides a splay-tree implementation of the `ORD_SET` signature parameterized over the element type.

`structure TimeLimit`

Provides a mechanism for limiting the execution time of a computation.

`structure UnivariateStats`

To be written

`structure URef`

Provides mutable references with Union-Find semantics.

`structure UTF8`

Provides support for working with UTF-8 encoded strings.

## Usage

By default, the Util Library is autoloaded by CM, which means that it is immediately available to interactive use in the SML/NJ REPL.

For SML/NJ, include `$/smlnj-lib.cm` in your CM file. For use in MLton, include `$(SML_LIB)/smlnj-lib/Util/smlnj-lib.mlb` in your MLB file.