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 EditDistance

Provides a function for computing Levenshtein between distance between strings.

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.

structure NativeInt

An alias to the native-sized integer structure (e.g., Int64).

structure NativeWord

An alias to the native-sized word structure (e.g., Word64).

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

Pseudo-random-number generation using the Mersenne Twister algorithm.

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.