Organization

The library is organized in structures (see notes on modules).

We can list the contents of a structure using open.

Example:

Standard ML of New Jersey v110.59 [built: Thu Jun  8 17:56:38 2006]
- open Int;
[autoloading]
[library $SMLNJ-BASIS/basis.cm is stable]
[autoloading done]
opening Int
  type int = ?.int
  val precision : Int31.int option
  val minInt : int option
  val maxInt : int option
  val toLarge : int -> IntInf.int
  val fromLarge : IntInf.int -> int
  val toInt : int -> Int31.int
  val fromInt : Int31.int -> int
  val ~ : int -> int
  val + : int * int -> int
  val - : int * int -> int
  val * : int * int -> int
  val div : int * int -> int
  val mod : int * int -> int
  val quot : int * int -> int
  val rem : int * int -> int
  val min : int * int -> int
  val max : int * int -> int
  val abs : int -> int
  val sign : int -> Int31.int
  val sameSign : int * int -> bool
  val > : int * int -> bool
  val >= : int * int -> bool
  val < : int * int -> bool
  val <= : int * int -> bool
  val compare : int * int -> order
  val toString : int -> string
  val fromString : string -> int option
  val scan : StringCvt.radix
             -> (char,'a) StringCvt.reader -> (int,'a) StringCvt.reader
  val fmt : StringCvt.radix -> int -> string
-

A warning: Opening a structure moves all definitions of a structure into the current environment (so that you can write maxInt instead of Int.maxInt). Sometimes this may lead to confusion. If you suspect that something has gone wrong, the solution may be to restart the SML system.

Let's take a look at Int.

- Int.maxInt;
val it = SOME 1073741823 : int option
- Int.minInt;
val it = SOME ~1073741824 : int option
-

Note that this is a smaller range than int in C (on a 32-bit machine)!

also try:

open Char;

and

open Real;

Note that all structures implement

val compare : int * int -> order

where order is defined:

datatype order = LESS
               | EQUAL
               | GREATER

Try Int.compare(5,7).

Also, try

open String;

Integers and integers

The signature for integers

(* integer.sig
 *
 * COPYRIGHT (c) 1995 AT&T Bell Laboratories.
 *
 *)

signature INTEGER =
  sig

    eqtype int

    val precision : Int.int option
    val minInt : int option
    val maxInt : int option

    val toLarge   : int -> LargeInt.int
    val fromLarge : LargeInt.int -> int
    val toInt     : int -> Int.int
    val fromInt   : Int.int -> int

    val ~ : int -> int
    val + : int * int -> int
    val - : int * int -> int
    val * : int * int -> int
    val div : int * int -> int
    val mod : int * int -> int
    val quot : int * int -> int
    val rem : int * int -> int

    val min : (int * int) -> int
    val max : (int * int) -> int

    val abs : int -> int

    val sign     : int -> Int.int
    val sameSign : (int * int) -> bool

    val >  : int * int -> bool
    val >= : int * int -> bool
    val <  : int * int -> bool
    val <= : int * int -> bool
    val compare : (int * int) -> order

    val toString   : int -> string
    val fromString : string -> int option
    val scan :
          StringCvt.radix -> (char, 'a) StringCvt.reader
            -> (int, 'a) StringCvt.reader
    val fmt  : StringCvt.radix -> int -> string

  end;

Structures that implement the interface:

Int
Int32
Int64
FixedInt
LargeInt

We have already seen Int.

Some experiments:

$ sml
Standard ML of New Jersey v110.67 [built: Mon Dec 10 09:56:06 2007]
- Int32.maxInt;
[autoloading]
[library $SMLNJ-BASIS/basis.cm is stable]
[autoloading done]
val it = SOME 2147483647 : Int32.int option
- Int64.maxInt;
[autoloading]
[autoloading done]
val it = SOME 9223372036854775807 : Int64.int option
- FixedInt.maxInt;
[autoloading]
[autoloading done]
val it = SOME 2147483647 : Int32.int option
- LargeInt.maxInt;
[autoloading]
[autoloading done]
val it = NONE : IntInf.int option
-

Some arithmetic leads us to conclude that while regular Int is stored in 31 bits, Int32 is 32 bit (same as the corresponding int type in C on most implementations) and Int64 is 64 bit.

FixedInt is (on my machine) another name for Int32.

But why does LargeInt.maxInt return NONE?

An experiment may give a hint. First change a system variable to allow printing of big numbers:

- Control.Print.intinfDepth := 10000;
val it = () : unit

Then create a large int equal to (almost) one million and start multiplying it to itself:

- LargeInt.fromInt 999999;
[autoloading]
[autoloading done]
val it = 999999 : IntInf.int
-  LargeInt.*(it, it);

val it = 999998000001 : IntInf.int
- -  LargeInt.*(it, it);

val it = 999996000005999996000001 : IntInf.int
- -  LargeInt.*(it, it);

val it = 9999920000279999440000699999440
00027999992000001 : IntInf.int
- -  LargeInt.*(it, it);

val it =
  99998400011999944000181999563200800798
8560012869988560008007995632001819999440
000119999984000001

  : IntInf.int
- -  LargeInt.*(it, it);

val it =
  99996800049599504003595979862490618863
4154518271951264512110975745792492626871
4350342778810798242777514352526266257927
1097558451221195121051829663414490619179
8624035959995040000495999968000001

  : IntInf.int
- -  LargeInt.*(it, it);

val it =
  999936[...]600001
  : IntInf.int

- -  LargeInt.*(it, it);

val it =
  999872[...]000001
  : IntInf.int
- -  LargeInt.*(it, it);

val it =
  999744[...]000001
  : IntInf.int
- -  LargeInt.*(it, it);

val it =
  999488[...]000001
  : IntInf.int
- -  LargeInt.*(it, it);

val it =
  998976[...]000001
  : IntInf.int
- -  LargeInt.*(it, it);

val it =
  997954[...]50017#
  : IntInf.int
- -

When the numbers become large, I only show the first six and last six digits. The last number ends with "#" because it contains more than 10000 digits.

The structure LargeInt allows arbitrarily large integers. The capacity of your computer sets limits on how big numbers it is practical to compute with, but in principle the integers represented by the LargeInt structure are unlimited.

Other basic structures

Real, List, String

Sets and maps

For those of you who know Java: They resemble the corresponding Java concepts.

The signature ORD_KEY

signature ORD_KEY =
sig
    type ord_key
    val compare : ord_key * ord_key -> order
end

We can easily define a structure that implements ORD_KEY, for example:

structure StringKey =
struct
    type ord_key = string
    val compare = String.compare
end;

Let's first take a look at the signature ord-map

(* ordset-sig.sml
 *
 * COPYRIGHT (c) 1993 by AT&T Bell Laboratories.  See COPYRIGHT file for details.
 *
 * Signature for a set of values with an order relation.
 *)

signature ORD_SET =
  sig

    structure Key : ORD_KEY

    type item = Key.ord_key
    type set

    val empty : set
	(* The empty set *)

    val singleton : item -> set
	(* Create a singleton set *)

    val fromList : item list -> set
	(* create a set from a list of items *)

    val add  : set * item -> set
    val add' : (item * set) -> set
	(* Insert an item. *)

    val addList : set * item list -> set
	(* Insert items from list. *)

    val delete : set * item -> set
	(* Remove an item. Raise NotFound if not found. *)

    val member : set * item -> bool
	(* Return true if and only if item is an element in the set *)

    val isEmpty : set -> bool
	(* Return true if and only if the set is empty *)

    val equal : (set * set) -> bool
	(* Return true if and only if the two sets are equal *)

    val compare : (set * set) -> order
	(* does a lexical comparison of two sets *)

    val isSubset : (set * set) -> bool
	(* Return true if and only if the first set is a subset of the second *)

    val numItems : set ->  int
	(* Return the number of items in the table *)

    val listItems : set -> item list
	(* Return an ordered list of the items in the set *)

    val union : set * set -> set
        (* Union *)

    val intersection : set * set -> set
        (* Intersection *)

    val difference : set * set -> set
        (* Difference *)

    val map : (item -> item) -> set -> set
	(* Create a new set by applying a map function to the elements
	 * of the set.
         *)

    val app : (item -> unit) -> set -> unit
	(* Apply a function to the entries of the set
         * in increasing order
         *)

    val foldl : (item * 'b -> 'b) -> 'b -> set -> 'b
	(* Apply a folding function to the entries of the set
         * in increasing order
         *)

    val foldr : (item * 'b -> 'b) -> 'b -> set -> 'b
	(* Apply a folding function to the entries of the set
         * in decreasing order
         *)

    val partition : (item -> bool) -> set -> (set * set)

    val filter : (item -> bool) -> set -> set

    val exists : (item -> bool) -> set -> bool

    val find : (item -> bool) -> set -> item option

  end (* ORD_SET *)

A lot of operations. You find (for example): create an empty set, add an element to a set (the set is not modified; a new one is created), check if an element is a member, check if one set is a subset of another, and create a list of all elements of a set.

But ORD_SET is just an interface; we need an implementation to be able to create sets.

The functor

RedBlackSetFn(K:ORD_KEY) : ORD_SET

gives us that.

For example;

structure SSet = RedBlackSetFn(StringKey);

creates an ordered set that uses red-black trees in the inderlying implementation and has strings for keys.

- SSet.empty;
val it = - : SSet.set
- SSet.add(it, "foo");
val it = - : SSet.set
- SSet.add(it, "bar");
val it = - : SSet.set
- SSet.listItems(it);
val it = ["bar","foo"] : SSet.item list

The signature ORD_MAP is similar:

(* ord-map-sig.sml
 *
 * COPYRIGHT (c) 1996 by AT&T Research.  See COPYRIGHT file for details.
 *
 * Abstract signature of an applicative-style finite maps (dictionaries)
 * structure over ordered monomorphic keys.
 *)

signature ORD_MAP =
  sig

    structure Key : ORD_KEY

    type 'a map

    val empty : 'a map
	(* The empty map *)

    val isEmpty : 'a map -> bool
	(* Return true if and only if the map is empty *)

    val singleton : (Key.ord_key * 'a) -> 'a map
	(* return the specified singleton map *)

    val insert  : 'a map * Key.ord_key * 'a -> 'a map
    val insert' : ((Key.ord_key * 'a) * 'a map) -> 'a map
	(* Insert an item. *)

    val find : 'a map * Key.ord_key -> 'a option
	(* Look for an item, return NONE if the item doesn't exist *)

    val lookup : 'a map * Key.ord_key -> 'a
	(* look for an item, raise the NotFound exception if it doesn't exist *)

    val inDomain : ('a map * Key.ord_key) -> bool
	(* return true, if the key is in the domain of the map *)

    val remove : 'a map * Key.ord_key -> 'a map * 'a
	(* Remove an item, returning new map and value removed.
         * Raises LibBase.NotFound if not found.
	 *)

    val first : 'a map -> 'a option
    val firsti : 'a map -> (Key.ord_key * 'a) option
	(* return the first item in the map (or NONE if it is empty) *)

    val numItems : 'a map ->  int
	(* Return the number of items in the map *)

    val listItems  : 'a map -> 'a list
    val listItemsi : 'a map -> (Key.ord_key * 'a) list
	(* Return an ordered list of the items (and their keys) in the map. *)

    val listKeys : 'a map -> Key.ord_key list
	(* return an ordered list of the keys in the map. *)

    val collate : ('a * 'a -> order) -> ('a map * 'a map) -> order
	(* given an ordering on the map's range, return an ordering
	 * on the map.
	 *)

    val unionWith  : ('a * 'a -> 'a) -> ('a map * 'a map) -> 'a map
    val unionWithi : (Key.ord_key * 'a * 'a -> 'a) -> ('a map * 'a map) -> 'a map
	(* return a map whose domain is the union of the domains of the two input
	 * maps, using the supplied function to define the map on elements that
	 * are in both domains.
	 *)

    val intersectWith  : ('a * 'b -> 'c) -> ('a map * 'b map) -> 'c map
    val intersectWithi : (Key.ord_key * 'a * 'b -> 'c) -> ('a map * 'b map) -> 'c map
	(* return a map whose domain is the intersection of the domains of the
	 * two input maps, using the supplied function to define the range.
	 *)

    val mergeWith : ('a option * 'b option -> 'c option)
	  -> ('a map * 'b map) -> 'c map
    val mergeWithi : (Key.ord_key * 'a option * 'b option -> 'c option)
	  -> ('a map * 'b map) -> 'c map
	(* merge two maps using the given function to control the merge. For
	 * each key k in the union of the two maps domains, the function
	 * is applied to the image of the key under the map.  If the function
	 * returns SOME y, then (k, y) is added to the resulting map.
	 *)

    val app  : ('a -> unit) -> 'a map -> unit
    val appi : ((Key.ord_key * 'a) -> unit) -> 'a map -> unit
	(* Apply a function to the entries of the map in map order. *)

    val map  : ('a -> 'b) -> 'a map -> 'b map
    val mapi : (Key.ord_key * 'a -> 'b) -> 'a map -> 'b map
	(* Create a new map by applying a map function to the
         * name/value pairs in the map.
         *)

    val foldl  : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
    val foldli : (Key.ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b
	(* Apply a folding function to the entries of the map
         * in increasing map order.
         *)

    val foldr  : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
    val foldri : (Key.ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b
	(* Apply a folding function to the entries of the map
         * in decreasing map order.
         *)

    val filter  : ('a -> bool) -> 'a map -> 'a map
    val filteri : (Key.ord_key * 'a -> bool) -> 'a map -> 'a map
	(* Filter out those elements of the map that do not satisfy the
	 * predicate.  The filtering is done in increasing map order.
	 *)

    val mapPartial  : ('a -> 'b option) -> 'a map -> 'b map
    val mapPartiali : (Key.ord_key * 'a -> 'b option) -> 'a map -> 'b map
	(* map a partial function over the elements of a map in increasing
	 * map order.
	 *)

  end (* ORD_MAP *)

There is a similar functor RedBlackMapFn that implements ORD_MAP.

- structure SMap = RedBlackMapFn(StringKey);
structure SMap : ORD_MAP?
- SMap.empty;
val it = - : 'a SMap.map
- SMap.insert(it, "foo", 37);
val it = - : int SMap.map
- SMap.insert(it, "bar", 42);
val it = - : int SMap.map
- val q = it;
val q = - : int SMap.map
- SMap.find(it, "foo");
val it = SOME 37 : int option
- SMap.find(q, "FOO");
val it = NONE : int option
- SMap.listItemsi(q);
val it = [("bar",42),("foo",37)] : (StringKey.ord_key * int) list

Functional programming
Notes on SML's Standard Library

Sven-Olof Nyström

Uppsala University

Organization

Integers and integers

Other basic structures

Sets and maps

Functional programming Notes on SML's Standard Library

Sven-Olof Nyström

Uppsala University

Organization

Integers and integers

Other basic structures

Sets and maps

Functional programming
Notes on SML's Standard Library