Module Prelude

OCaml Standard Library additions and renamings.

See the Example.

Philosophy and Usage

You'll notice that I much prefer terse function names, especially since OCaml's nestable module system provides ready access to longer names via the module prefixes, and OCaml's local-open syntax allows these short names to be easily used without global namespace contamination.

Incompatibilities With Stdlib When You open Prelude

Occasionally new functions are added to Stdlib modules, like Stdlib.List, whose names are already used in Prelude; this is something to be aware of if you open Prelude as I do. An example is that recently Stdlib.List acquired a compare function. Since Prelude opens List, this new compare would shadow Stdlib.compare, which is IMHO annoying.

My fix is to arrange that Prelude.compare is Stdlib.compare. The downside is that if you want Stdlib.List.compare you have to use the fully-qualified name, even though you've implicitly open'ed List. Since Stdlib.List.compare has a different type than Stdlib.compare, you'll always get a compile-time error if you ever get confused.

If there's anything about this you don't like, you can simply use Prelude without opening it.

Conventions for Data Types and Modules

Aspirationally, all modules that define data types should include the following functions:

I find these functions to be extremely useful for development and testing (especially in the top-level), and for unit tests.

Classified Index

Acknowledgements

Many thanks to Matt TEICHMAN for lots of consultation, type wizardry, and especially for figuring out how to solve the dreaded int List.t = (::) (1, [2; 3]) top-level bug.

Combinators and Operators

val id : 'a -> 'a

id x: identity function (I combinator), returns x.

val k : 'a -> 'b -> 'a

(k x y) is x; this is the constant function generator (K combinator).

val ki : 'a -> 'b -> 'b

(ki x y) is y; ki = (flip k) and is KI in combinatory logic.

val flip : ('a -> 'b -> 'c) -> 'b -> 'a -> 'c

flip f x y: argument-flipping combinator (C combinator); returns (f y x). (flip (^) "a" "b") = "ba"

val w : ('a -> 'a -> 'b) -> 'a -> 'b

(w f x) is (f x x); this is the argument-doubling combinator W.

val dbl : ('a -> 'a -> 'b) -> 'a -> 'b

dbl is w.

val whenever : 'a -> 'a -> 'a -> 'a

(whenever this that x) is (if x = this then that else x).

Example:

(argv |> whenever [] ["-"] |> iter (within process))

will invoke process on stdin if no files are in argv.

val curry : (('a * 'b) -> 'c) -> 'a -> 'b -> 'c

(curry f): converts a function on pairs to a curried function of two arguments.

val uncurry : ('a -> 'b -> 'c) -> ('a * 'b) -> 'c

(uncurry f): converts a curried function of two arguments to a function on pairs.

val tap : ('a -> unit) -> 'a -> 'a

(tap f x): applies (f x) for side-effect, then returns x. ("foo" |> tap print |> String.length) prints "foo" and returns 3.

val (|-) : 'a -> ('a -> 'b) -> 'a

(|-) is (flip tap).

foo
|> List.map ...
|- (len >> printf "%d\n")
|> List.concat
|> ...
  • author Idea due to Xavier Clerc.
val thunk : ('a -> 'b) -> 'a -> unit -> 'b

(thunk f x) is (fun () -> f x), i.e. it wraps the application (f x) in a thunk.

val y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

y is the fixed-point finding Y-combinator; not tail-recursive.

y can be used to write recursive functions without using let rec: for example, given:

let fact_ fact x = if x = 0 then 1 else x * fact (x-1)

then (y fact_ 6) = 720.

Perhaps more practically, y can be used, for example to trace a recursive function without signifcantly modifying the function definition:

let trace name f_ f x = let r = f_ f x in printf "%s %d -> %d\n" name x r; r

and now:

    # y (trace "fact" fact_) 6;;
    fact 0 -> 1
    fact 1 -> 1
    fact 2 -> 2
    fact 3 -> 6
    fact 4 -> 24
    fact 5 -> 120
    fact 6 -> 720
    _ : int = 720
val fork : ('a -> 'b -> 'c) -> ('d -> 'a) -> ('d -> 'b) -> 'd -> 'c

(fork (±) f g x) is (f x ± g x) and is the unary version of fork2.

N.B. this is J's fork conjunction (with monadic f and g, and dyadic (±)).

     ±
    / \
   f   g
   |   |
   x   y

Example: (fork (/) sum len) is the arithmetic mean:

  • (fork (/) sum len (1--100)) = 50

Example: (fork (-) maximum minimum) is the range of the ints in its list argument:

  • (fork (-) maximum minimum [2;8;5;4]) = 6
val fork2 : ('a -> 'b -> 'c) -> ('d -> 'e -> 'a) -> ('d -> 'e -> 'b) -> 'd -> 'e -> 'c

(fork2 (±) ( × ) (÷) n m) is (n×m + n÷m) for arbitrary functions (+), ( × ), and (÷).

N.B. this is J's fork conjunction (with dyadic (±), ( × ), and (÷)).

      ±
    /   \
   ×     ÷
  / \   / \
 n   m n   m
val lefthook : ('a -> 'b -> 'c) -> ('d -> 'a) -> 'd -> 'b -> 'c

(lefthook (±) (¬) x y) is (¬x ± y).

     ±
    / \
   ¬   y
   |
   x

Example: (lefthook cons succ) = (conswith succ)

Example: fastest way to get the size of the data on an input channel like stdin:

Gen.(optional readblock $ fold (lefthook (+) String.len) 0)
val (<?) : ('a -> 'b -> 'c) -> ('d -> 'a) -> 'd -> 'b -> 'c

(<?) is lefthook.

Example: foldr (cons <? even) [] (0--4) = [true; false; true; false; true]

val righthook : ('a -> 'b -> 'c) -> ('d -> 'b) -> 'a -> 'd -> 'c

(righthook (±) (¬) x y) is (x ± ¬y).

     ±
    / \
   x   ¬
       |
       y

Example: (righthook snoc succ) = (snocwith succ)

val (>?) : ('a -> 'b -> 'c) -> ('d -> 'b) -> 'a -> 'd -> 'c

(>?) is righthook.

Example: foldl (snoc >? even) [] (0--4) = [true; false; true; false; true]

val on : ('a -> 'a -> 'b) -> ('c -> 'a) -> 'c -> 'c -> 'b

on (±) (¬) is (fun x y -> ¬x ± ¬y). Typically used to generate comparison functions for List.sort.

     ±
    / \
   ¬   ¬
   |   |
   x   y

For example, to sort an alist in reverse order of values, use:

(sort (on (flip compare) snd))
val on1 : ('a -> 'a -> 'b) -> ('c -> 'a) -> 'c -> 'b

(on1 (±) (¬) x) is (fork (±) (¬) (¬)) i.e. (¬x ± ¬x).

     ±
    / \
   ¬   ¬
   |   |
   x   x

Example: (on1 ( + ) (dbl ( * ))) x = (x*x) + (x*x)

Comparison

A comparison function is one that compares two values and returns one of (-1, 0, 1) (e.g. OrderedType.compare).

See also Lists.comparison and AIString.compare.

val revcmp : ('a -> 'b -> int) -> 'b -> 'a -> int

(revcmp cmp) converts the comparison function cmp to one that compares in reverse order.

val cmpeq : ('a -> 'b -> int) -> 'a -> 'b -> bool

(cmpeq cmp) converts the comparison function cmp into an equality predicate.

Relational Operators for Partial Application

These functions are flipped versions of the standard relational operators (<), (<=), (>), and (>=) (I throw in (=) and (<>) just for symmetry) and are intended to be used partially-applied. I think this function:

(len >> gt 64)

looks much better and is easier to understand than:

(len >> flip (>) 64)

or:

(len >> fun n -> n > 64)

or even, sometimes:

(fun xs -> len xs > 64)

YMMV!

val lt : 'a -> 'a -> bool

(lt n) is true iff it is applied to a value strictly less than n.

lt is (flip (<)).

val lte : 'a -> 'a -> bool

(lte n) is true iff it is applied to a value less than or equal to n.

lte is (flip (<=)).

val gt : 'a -> 'a -> bool

(gt n) is true iff it is applied to a value strictly greater than n.

gt is (flip (>)).

val gte : 'a -> 'a -> bool

(gte n) is true iff it is applied to a value greater than or equal to n.

gte is (flip (>=)).

val eq : 'a -> 'a -> bool

(eq n) is true iff it is applied to a value equal to n.

eq is just (=).

val neq : 'a -> 'a -> bool

(neq n) is true iff it is applied to a value not equal to n.

neq is just (<>).

Function Composition and Application

val apply : ('a -> 'b) -> 'a -> 'b

(apply f x): function application: (apply f x) is exactly equivalent to (f x).

val (@@) : ('a -> 'b) -> 'a -> 'b

(@@) is apply; right associative.

This is Haskell's ($), and is useful for eliminating parentheses.

Example:

(print_endline (string_of_int (1 + 1))) = (print_endline @@ string_of_int @@ 1 + 1)
val (<<) : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b

(f << g): function composition: ((f << g) x) is exactly equivalent to (f (g x)).

This is Haskell's (.).

val ($.) : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b
  • deprecated

    Use (<<).

val (>>) : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c

(f >> g): reverse function composition: ((f >> g) x) is exactly equivalent to (g (f x)).

val ($) : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c
  • deprecated

    Use (>>).

Exception

exception Failed_prerequisite of string list

(Failed_prerequisite cmds) is the type of exceptions raised by functions in Prereq.

Module Types

Null

module type NULL = sig ... end

The empty module.

module Null : NULL

OrderedType

module type OrderedType = sig ... end

(sig type t val compare : t -> t -> int end).

TOSTRING

module type TOSTRING = sig ... end

(sig type t val to_string : t -> string end).

ARITH

module type ARITH = sig ... end

Signature for Arithmetics (type t, zero, succ, ( + ) and ( * )); we also include compare, one, pred, ( - ), ( / ), and random.

Bool

module Bool : sig ... end

Prelude.Bool is Stdlib.Bool with additional Boolean functions; satisifes OrderedType.

N0: The Natural Numbers from zero.

module N0 : sig ... end

Type-specialized comparison; satisifes OrderedType.

N1: The Natural Numbers from one.

module N1 : sig ... end

Type-specialized comparison; satisifes OrderedType.

Int

module Int : sig ... end

Type-specialized operators and comparisons; satisifes ARITH.

Arithmetic

val (~++) : int -> int

(~++) x is (succ x); like C's ++; minimizes parens in function parameters.

val (~--) : int -> int

(~--) x is (pred x); like C's --; minimizes parens in function parameters.

val even : int -> bool

(even n) is true iff n is an even integer.

val odd : int -> bool

(odd n) is true iff n is an odd integer.

Float

module Float : sig ... end

Type-specialized operators and comparisons; satisifes ARITH.

val round : float -> float

round is Float.round.

Pairs

module Pair : sig ... end

Useful functions on 2-tuples.

val (&&&) : ('a -> 'b) -> ('c -> 'd) -> ('a * 'c) -> 'b * 'd

(&&&) is Pair.cross.

val (***) : ('a -> 'b) -> ('a -> 'c) -> 'a -> 'b * 'c

( *** ) is Pair.diag.

Triples

module T3 : sig ... end

Useful functions on 3-tuples.

Interval

module Interval : sig ... end

Interval arithmetic over a type T: ARITH.

val between : ('a * 'a) -> 'a -> bool

between is Interval.Int.between.

val contains : ('a * 'a) -> 'a -> bool

contains is Interval.Int.contains.

val inbounds : ('a * 'a) -> 'a -> bool

inbounds is Interval.Int.inbounds.

Refs

val (+:=) : int Stdlib.ref -> int -> unit

(r +:= n) increments the int in r by n; like C's +=.

val (-:=) : int Stdlib.ref -> int -> unit

(r -:= n) decrements the int in r by n; like C's -=.

val (*:=) : int Stdlib.ref -> int -> unit

(r *:= n) multiplies the int in r by n; like C's *=.

val (/:=) : int Stdlib.ref -> int -> unit

(r /:= n) divides the int in r by n; like C's /=.

val (@:=) : 'a list Stdlib.ref -> 'a -> unit

(r @:= x) conses x onto the list in ref r. N.B. conses not appends.

I'd prefer to use (::=) as the operator, but OCaml syntax doesn't allow it.

Printf

include module type of struct include Stdlib.Printf end
val fprintf : Stdlib.out_channel -> ('a, Stdlib.out_channel, unit) Stdlib.format -> 'a
val printf : ('a, Stdlib.out_channel, unit) Stdlib.format -> 'a
val eprintf : ('a, Stdlib.out_channel, unit) Stdlib.format -> 'a
val sprintf : ('a, unit, string) Stdlib.format -> 'a
val bprintf : Stdlib.Buffer.t -> ('a, Stdlib.Buffer.t, unit) Stdlib.format -> 'a
val ifprintf : 'b -> ('a, 'b, 'c, unit) Stdlib.format4 -> 'a
val ibprintf : Stdlib.Buffer.t -> ('a, Stdlib.Buffer.t, unit) Stdlib.format -> 'a
val kfprintf : (Stdlib.out_channel -> 'd) -> Stdlib.out_channel -> ('a, Stdlib.out_channel, unit, 'd) Stdlib.format4 -> 'a
val ikfprintf : ('b -> 'd) -> 'b -> ('a, 'b, 'c, 'd) Stdlib.format4 -> 'a
val ksprintf : (string -> 'd) -> ('a, unit, string, 'd) Stdlib.format4 -> 'a
val kbprintf : (Stdlib.Buffer.t -> 'd) -> Stdlib.Buffer.t -> ('a, Stdlib.Buffer.t, unit, 'd) Stdlib.format4 -> 'a
val ikbprintf : (Stdlib.Buffer.t -> 'd) -> Stdlib.Buffer.t -> ('a, Stdlib.Buffer.t, unit, 'd) Stdlib.format4 -> 'a
val kprintf : (string -> 'b) -> ('a, unit, string, 'b) Stdlib.format4 -> 'a
val (%) : ('a -> 'b, unit, string) Stdlib.format -> 'a -> 'b

(fmt % x) is (sprintf fmt x).

Exceptions

module Exn : sig ... end

Functions for working with exceptions.

val finalize : ('a -> 'b) -> ('a -> unit) -> 'a -> 'b

finalize is Exn.finalize

val succeeds : ('a -> 'b) -> 'a -> bool

succeeds is Exn.succeeds

val default : 'a -> ('b -> 'a) -> 'b -> 'a

default is Exn.default

val reraise : ?this:exn -> exn -> ('a -> 'b) -> 'a -> 'b

reraise is Exn.reraise

Functionals

val foldil : ('a -> int -> 'a) -> 'a -> (int * int) -> 'a

foldil is Interval.Int.foldil.

val foldir : (Int.t -> 'a -> 'a) -> 'a -> (Int.t * Int.t) -> 'a

foldir is Interval.Int.foldir.

val foreach : (Int.t -> 'a) -> (Int.t * Int.t) -> unit

foreach is Interval.Int.foreach.

val foldex : ?exn:exn -> ('a -> 'b -> 'b) -> 'b -> 'a -> 'b

foldex is Exn.fold.

val whilst : ('a -> bool) -> ('a -> 'a) -> 'a -> 'a

(whilst p f x) is a functional while-loop; it is (f ( ... (f (f x)))) while (p x) is true.

The quaint name is because while is an OCaml keyword.

Example: (whilst (function x::_ -> x <= 10 | [] -> false) tl) = (dropwhile (fun x -> x <= 10))

val until : ('a -> bool) -> ('a -> 'a) -> 'a -> 'a

(until p f x) is a functional repeat-until-loop; it is whilst (not << p) f (f x).

val iff : ('a -> bool) -> ('a -> 'b) -> ('a -> 'b) -> 'a -> 'b

(iff p consequent alternative x) is if p x then consequent x else alternative x.

Examples: (iff even cons (fun _ xs -> xs)) = (conswhen even)

(foldr (iff even cons (fun _ xs -> xs)) [] (1--20)) = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]
val onlyif : ('a -> bool) -> ('a -> 'a) -> 'a -> 'a

(onlyif p f x) is (f x) iff (p x) and is x otherwise.

Example: (map (onlyif even (k 0)) (1--10)) = [1; 0; 3; 0; 5; 0; 7; 0; 9; 0]

Seq

module Seq : sig ... end

Functional Iterators

Options

module Option : sig ... end

Option monad and other useful functions on options.

val catch : ?this:exn -> ('a -> 'b) -> 'a -> 'b Option.t

catch is Option.catch

val some : 'a -> 'a Option.t

some is Option.some

val none : 'a option

none is Option.none

val something : 'a Option.t -> bool

something is Option.something

val nothing : 'a Option.t -> bool

nothing is Option.nothing

Results

module Result : sig ... end

Result (error) monad.

Buffer

module Buffer : sig ... end

Additional Buffer functions.

val withbuf2 : int -> (Stdlib.Buffer.t -> 'a) -> string * 'a

withbuf2 is Buffer.withbuf2.

val withbuf : int -> (Stdlib.Buffer.t -> 'a) -> string

withbuf is Buffer.withbuf.

Lists

module Lists : sig ... end

Additional List functions and renamings.

module List : sig ... end

This is Ocaml's standard List with the additional functions from Lists.

List is opened.

include module type of struct include List end

This is Ocaml's standard List with the additional functions from Lists.

module type LIST = List.LIST
type 'a t = 'a list
include LIST
val length : 'a list -> int
val compare_lengths : 'a list -> 'b list -> int
val compare_length_with : 'a list -> int -> int
val nth : 'a list -> int -> 'a
val nth_opt : 'a list -> int -> 'a option
val append : 'a list -> 'a list -> 'a list
val rev_append : 'a list -> 'a list -> 'a list
val flatten : 'a list list -> 'a list
val equal : ('a -> 'a -> bool) -> 'a list -> 'a list -> bool
val rev_map : ('a -> 'b) -> 'a list -> 'b list
val filter_map : ('a -> 'b option) -> 'a list -> 'b list
val concat_map : ('a -> 'b list) -> 'a list -> 'b list
val fold_left_map : ('a -> 'b -> 'a * 'c) -> 'a -> 'b list -> 'a * 'c list
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a
val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c
val for_all : ('a -> bool) -> 'a list -> bool
val exists : ('a -> bool) -> 'a list -> bool
val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
val memq : 'a -> 'a list -> bool
val find : ('a -> bool) -> 'a list -> 'a
val find_opt : ('a -> bool) -> 'a list -> 'a option
val find_map : ('a -> 'b option) -> 'a list -> 'b option
val find_all : ('a -> bool) -> 'a list -> 'a list
val filteri : (int -> 'a -> bool) -> 'a list -> 'a list
val partition_map : ('a -> ('b, 'c) Stdlib.Either.t) -> 'a list -> 'b list * 'c list
val assoc : 'a -> ('a * 'b) list -> 'b
val assoc_opt : 'a -> ('a * 'b) list -> 'b option
val assq : 'a -> ('a * 'b) list -> 'b
val assq_opt : 'a -> ('a * 'b) list -> 'b option
val mem_assoc : 'a -> ('a * 'b) list -> bool
val mem_assq : 'a -> ('a * 'b) list -> bool
val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
val combine : 'a list -> 'b list -> ('a * 'b) list
val sort : ('a -> 'a -> int) -> 'a list -> 'a list
val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list
val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list
val sort_uniq : ('a -> 'a -> int) -> 'a list -> 'a list
val merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
val to_seq : 'a list -> 'a Stdlib.Seq.t
val of_seq : 'a Stdlib.Seq.t -> 'a list
include module type of struct include Lists end

Additional List functions and renamings.

We also include all the List functions that we want when we include Lists in Prelude.

Basic Functions

val len : 'a list -> int

len is List.length.

val comparison : ('a -> 'a -> int) -> 'a list -> 'a list -> int

comparison is Stdlib.List.compare.

val to_string : ?left:string -> ?sep:string -> ?right:string -> ('a -> string) -> 'a list -> string

(to_string ?left ?sep ?right f xs) returns a string representation of xs.

f is used for the string representation of each element of xs.

The representation of the list is inserted between ?left (default: "[") and ?right (default: "]"); each element of xs is separated by ?sep (default: "; ").

Example: (to_string string_of_int (1--10)) = "[1; 2; 3; 4; 5; 6; 7; 8; 9; 10]"

val hd : 'a list -> 'a

(hd xs) is the first element of xs.

  • raises Failure

    if the list is empty.

val head : 'a list -> 'a option

(head xs) is None if (xs = []) and (Some (hd xs)) otherwise.

val init : 'a list -> 'a list

(init xs) is all the elements of xs except the last one; tail-recursive

(init xs) = (rev $ tl $ rev)
  • raises Failure

    if the list is empty.

val tl : 'a list -> 'a list

(tl (x::xs)) is xs.

  • raises Failure

    if the list is empty.

val tail : 'a list -> 'a list option

(tail xs) is None if (xs = []) and (Some (tl xs)) otherwise.

val last : 'a list -> 'a

(last xs) is the last element of xs; tail-recursive.

(last xs) = (hd (rev xs))
  • raises Failure

    if the list is empty.

val get : int -> 'a list -> 'a

(get) is (flip List.nth).

Building Lists

val cons : 'a -> 'a list -> 'a list

cons is List.cons.

val snoc : 'a list -> 'a -> 'a list

snoc is (flip cons).

val consup : 'a -> 'a list

(consup x) is (x::[]).

val revcons : 'a -> 'a list -> 'a list

(revcons) is (xs @ [x]).

val unfoldr : ('a -> bool) -> ('a -> 'b) -> ('a -> 'a) -> 'a -> 'b list

(unfoldr p f g x) builds a list (f x :: unfoldr p f g (g x)) from a seed value x until ((p x) = true). Not tail-recursive.

Example:

  • (unfoldr ((=) 0) id pred 10) = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1]
val make : int -> (int -> 'a) -> 'a list

(make n f) is [f 0; f 1; ...; f (n-1)], evaluated left to right. Tail-recursive.

Example: a list of 10 random integers in the range 0-99:

make 10 (fun _ -> Random.int 100)
val repeat : int -> 'a -> 'a list

(repeat n x) is the list of exactly n x's.

val trappend : 'a list -> 'a list -> 'a list

trappend is a tail-recursive List.append.

val prepend : 'a list -> 'a list -> 'a list

(prepend xs ys) prepends xs onto the front of ys and is another name for List.append.

val postpend : 'a list -> 'a list -> 'a list

(postpend xs ys) postpends xs onto the end of ys and is the same as (flip List.append).

val scanl : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a list

(scanl f z list) is similar to foldl, but returns a list of successive reduced values from the left:

scanl (±) z [x1; x2; ...] = [z; z ± x1; (z ± x1) ± x2; ...]

Invariant: (last (scanl f z xs)) = (foldl f z xs)

val eachpair : ('a -> 'a -> 'b) -> 'a list -> 'b list

(eachpair f list) applies f to each consecutive pair of elements in list.

Example: (eachpair f [1;2;3;4]) = (f 1 2 :: f 2 3 :: f 3 4 :: [])

Invariants:

  • ∀f.(eachpair f []) = []
  • ∀f.∀x.(eachpair f [x]) = []
  • ∀f.∀xs.xs = [] || (len (eachpair f xs)) = (len xs - 1)
val permutations : 'a list -> 'a list list

(permutations xs) is the list of all permutations of xs; not tail-recursive. O(n!).

  • author Michel Quercia
val upto : int -> int -> int list

(upto m n) is the list of ints in the interval [m,n] (tail-recursive).

(upto 1 5) = [1; 2; 3; 4; 5].

Random Value

val random : ?size:(unit -> int) -> (unit -> 'a) -> unit -> 'a list

(random ?size r ()) is a list of size (size ()) (default: < 100); the elements are given by (r ()).

Predicates

val null : 'a list -> bool

(null xs) is true iff (xs = []).

val empty : 'a list -> bool

empty is null.

val nonempty : 'a list -> bool

(nonempty xs) is true iff (not (null xs)).

val singleton : 'a list -> bool

(singleton xs) is true iff (len xs = 1), O(1).

val many : 'a list -> bool

(many xs) is true iff (len xs > 1), O(1).

val prefix : 'a list -> 'a list -> bool

(prefix pat subj) is true if pat is a prefix of subj and false otherwise.

Invariants:

  • ∀xs : (prefix [] xs) = true
  • ∀xs : (prefix xs xs) = true
  • ∀xs : (xs = [] || prefix (init xs) xs) = true

Reducing Lists (Folds)

val foldl : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

foldl is List.fold_left.

val foldr : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b

(foldr f z xs) is (List.fold_right f xs z).

This order of parameters is much more useful in conjunction with the (|>)-operator.

val foldl1 : ('a -> 'a -> 'a) -> 'a list -> 'a

foldl1 is foldl with no initial accumulator value, and thus must be applied to non-empty lists.

  • raises Invalid_argument

    if the list is empty.

val foldr1 : ('a -> 'a -> 'a) -> 'a list -> 'a

foldr1 is foldr with no initial accumulator value, and thus must be applied to non-empty lists.

  • raises Invalid_argument

    if the list is empty.

val foldl2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a

foldl2 is List.fold_left2.

val foldr2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c

foldr2 is List.fold_right2.

val foldwise : ?skip:bool -> int -> ('a -> 'b list -> 'a) -> 'a -> 'b list -> 'a

(foldwise ?skip n f init xs) left-fold f across sequential non-overlapping n-wise subsequences of xs; tail-recursive.

For example, (foldwise 2) is a pairwise fold:

 foldwise 2 (snocwith rev) [] (1--12) |> rev
= [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]; [11; 12]]

f is given an accumulator and a sublist of length n. For efficiency, the sublists passed to f will be in the reverse of the order in which they occur in xs; f can reverse them if necessary.

Unless skip is true, f must be prepared to receive a final sublist of length less than n if the length of xs is not evenly divisible by n.

If (skip = true), only the initial (len xs - ((len xs) mod n)) elements of xs will be processed.

Invariants:

  • (foldwise n (snocwith rev) [] xs |> rev |> flatten) = xs
  • (foldwise n ~skip:false f init (take (len xs - len xs mod n) xs)) = (foldwise n ~skip:true f init xs)

Fold Helpers

Functions useful with foldl and foldr.

val conswith : ('a -> 'b) -> 'a -> 'b list -> 'b list

(conswith f) is (cons <? f) and also (fun x xs -> f x :: xs).

val conswhen : ('a -> bool) -> 'a -> 'a list -> 'a list

(conswhen p x xs) is (cons x xs) when p x = true and otherwise is xs.

foldr (conswhen Int.even) [] (1--10) = [2; 4; 6; 8; 10]
val snocwith : ('a -> 'b) -> 'b list -> 'a -> 'b list

(snocwith f) is (flip (conswith f)). Suitable for foldl.

(fun f -> foldl (snocwith f) [] $ rev) is a tail-recursive map.

val snocwhen : ('a -> bool) -> 'a list -> 'a -> 'a list

(snocwhen p) is (flip (conswhen p)). Suitable for foldl.

Special Folds

val concat : 'a list list -> 'a list

concat is List.concat.

val anded : bool list -> bool

(anded bools) is the conjunction of the Booleans in bools.

val ored : bool list -> bool

(ored bools) is the disjunction of the Booleans in bools.

val conjunction : ('a -> bool) list -> 'a -> bool

(conjunction ps x) is the conjunction of the predicates in ps.

val disjunction : ('a -> bool) list -> 'a -> bool

(disjunction ps x) is the disjunction of the predicates in ps.

val all : ('a -> bool) -> 'a list -> bool

(all p xs) is true if (p x) for all of the xs.

Invariant:

  • (all p xs) = (map p xs |> anded)
val any : ('a -> bool) -> 'a list -> bool

(any p xs) is true if (p x) for any of the xs.

Invariant:

  • ∀p : ∀xs : (any p xs) = (map p xs |> ored)
val sum : int list -> int

(sum xs) is the sum of the ints in xs.

val product : int list -> int

(product xs) is the product of the ints in xs.

val maximumBy : ?compare:('a -> 'a -> int) -> 'a list -> 'a

(maximumBy compare xs) is the maximum of the xs according to compare.

Examples:

  • maximumBy compare (1--10) = 10 
  • maximumBy compare ["zap";"foo"] = "zap" 
  • maximumBy compare ["ZAP";"foo"] = "foo" 
  • maximumBy AIString.compare ["ZAP";"foo"] = "ZAP" 
  • maximumBy AIString.compare ["zap";"foo"] = "zap"
  • raises Invalid_argument

    if the list is empty.

val maximum : 'a list -> 'a

maximum is (maximumBy compare).

Examples:

  • maximum (1--10) = 10 
  • maximum ["zap";"foo"] = "zap" 
  • maximum  ["ZAP";"foo"] = "foo"
  • raises Invalid_argument

    if the list is empty.

val minimum : ?compare:('a -> 'a -> int) -> 'a list -> 'a

(minimum ?compare xs) is the minimum of the xs. If provided, compare is used for comparison (default: polymorphic minimum via min).

Examples:

  • minimum (1--10) = 1 
  • minimum ["zap";"foo"] = "foo" 
  • minimum  ["ZAP";"foo"] = "ZAP" 
  • minimum ~compare:AIString.compare ["ZAP";"foo"] = "foo" 
  • minimum ~compare:AIString.compare ["zap";"foo"] = "foo"
  • raises Invalid_argument

    if the list is empty.

val break : ('a -> 'a -> bool) -> 'a list -> 'a list list

(break eq list) does control-break processing on the (typically sorted) list, grouping together consecutive subsequences of elements which are equal under eq.

N.B. For the sake of efficiency, the result is in reverse order, as are all the sublists. (List.rev_map rev) will restore order.

Example: this function:

  • (break (fun p x -> p.[0] = x.[0]))

will group a sorted list of words into lists of words that begin with the same letter.

["copulatives"; "cumulative"; "deliverable"; "denial"; "drowning";
"folklorists"; "gradualism"; "lowliest"; "orangeade"; "oxen"]
|> break (fun p x -> p#!0 = x#!0) |> List.rev_map rev
= [["copulatives"; "cumulative"]; ["deliverable"; "denial"; "drowning"];
["folklorists"]; ["gradualism"]; ["lowliest"]; ["orangeade"; "oxen"]]

List Transformations

val rev : 'a list -> 'a list

rev is List.rev.

val map : ('a -> 'b) -> 'a list -> 'b list

map is List.map.

val trmap : ('a -> 'b) -> 'a list -> 'b list

trmap is a tail-recursive map.

val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list

mapi is List.mapi.

val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list

map2 is List.map2.

val flatmap : ('a -> 'b list) -> 'a list -> 'b list

(flatmap f) is a tail-recursive (map f $ concat).

  • author Matt Teichman
val filter : ('a -> bool) -> 'a list -> 'a list

filter is List.filter.

val delete : ?eq:('a -> 'a -> bool) -> 'a -> 'a list -> 'a list

(delete ?eq x xs) removes the first occurrence of x from xs; tail recursive.

val replace : 'a -> 'a -> 'a list -> 'a list

(replace sub rep xs) replaces each occurrence of sub in xs with rep.

Examples:

  • (replace 1 10 (1--6)) = [10; 2; 3; 4; 5; 6]
  • (replace 10 20 (1--6)) = [1; 2; 3; 4; 5; 6]
  • ((1--6) |> map (flip (mod) 2) |> replace 0 2) = [1; 2; 1; 2; 1; 2]
val behead : 'a list -> 'a list -> 'a list

(behead prefix list) is the remainder of list when the leading prefix is removed.

prefix must be an exact prefix of list for anything to be removed.

Invariants:

  • (behead [] xs) = xs
  • (behead xs []) = []
  • (behead xs xs) = []
  • (behead (x::xs) xs) = xs
  • (len (behead xs ys)) <= (len ys)
  • (prefix xs ys) && (behead xs ys) <> ys
val prefixes : 'a list -> 'a list list

(prefixes xs) is the list of all prefixes of xs.

(prefixes [1;2;3]) = [[]; [1]; [1; 2]; [1; 2; 3]]

Invariants:

  • (prefixes xs) = (scanl snoc [] xs |> map rev)
  • (prefixes xs |> map (flip prefix xs) |> anded) = true
  • (prefixes xs |> hd) = []
val suffixes : 'a list -> 'a list list

(suffixes xs) is the list of all suffixes of xs.

(suffixes [1;2;3]) = [[]; [3]; [2; 3]; [1; 2; 3]]

Invariant: (suffixes xs |> hd) = []

val intersperse : 'a -> 'a list -> 'a list

(intersperse x xs) inserts x between the elements of xs.

Example: String.(explode "123456" |> intersperse ',' |> implode) = "1,2,3,4,5,6"

Invariants:

  • (intersperse x []) = []
  • (intersperse x [y]) = [y]
val pad : ?left:bool -> def:'a -> int -> 'a list -> 'a list

(pad ?(left=false) ~def n xs) pads xs on the right (or on the left, if (left = true)) with enough instances of def such that the length of the result is at least n.

If you need the result list to be exactly of length n (never longer), use:

  • (take n $ pad ~def n)

Invariant: (len (pad ~left ~def n xs) = max n (len xs))

val transpose : ?def:'a -> 'a list list -> 'a list list

(transpose ?def xss) is the transposition of the rows and columns of xss; tail recursive.

Unless def is provided, if any sublist is shorter than the first sublist, (Invalid_argument _) is raised. Otherwise, the resulting sublists will all be of length (len (nth xss 0)).

If def is provided, it serves as a default element that is appended as needed to bring all lists to the length of the longest list in xss; in this case, the "matrix" is guaranteed to be rectangular and no exception will be raised.

Examples:

  • transpose [1--3;4--6] = [[1; 4]; [2; 5]; [3; 6]]
  • transpose [[1];[1;2]] = [[1; 1]]
  • catch transpose [[1;2];[1]] = None
  • transpose ~def:0 [[1;2];[1]] = [[1; 1]; [2; 0]]
val evens : 'a list -> 'a list

(evens xs) is all the elements of xs at even indexes.

  • evens [1; 3; 5] = [1; 5]
  • evens ["a"; "b"; "c"] = ["a"; "c"]
val odds : 'a list -> 'a list

(odds xs) is all the elements of xs at odd indexes.

  • odds [0; 2; 4] = [2]
  • odds ["a"; "b"; "c"] = ["b"]

Sublists

val splitat : int -> 'a list -> 'a list * 'a list

(splitat n xs) is (a,b) such that a is the length-n prefix of xs, and b is the remainder of the xs.

It is equivalent to (take n xs, drop n xs), but makes only one pass.

Invariant:

  • let a,b = splitat n xs in prefix a xs && (a @ b) = xs

Examples:

  • splitat 3 [1;2;3;4;5] = [1;2;3], [4;5]
  • splitat 1 [1;2;3] = [1], [2;3]
  • splitat 3 [1;2;3] = [1;2;3], []
  • splitat 4 [1;2;3] = [1;2;3], []
  • splitat 0 [1;2;3] = [], [1;2;3]
  • splitat ~-1 [1;2;3] = [], [1;2;3]
val everyother : 'a list -> 'a list

(everyother xs) is the list consisting of every other element of xs, starting with the first; O(n), 1-pass algorithm.

Invariants:

  • (len (everyother xs) = if even (len xs) then len xs / 2 else len xs / 2 + 1)
  • (hd (everyother xs) = hd xs)
val take : int -> 'a list -> 'a list

(take n xs) is (splitat n >> fst).

Invariant: (take n xs) = (drop (len xs - n) (rev xs) |> rev)

val drop : int -> 'a list -> 'a list

(drop n xs) is (splitat n >> snd).

Invariant: (drop n xs) = (take (len xs - n) (rev xs) |> rev)

val takeall : int -> 'a list -> 'a list list

(takeall n list) returns the sequential sublists of length n in list.

If n <= 0, the empty list is returned.

Invariant:

  • ∀n . n>0 : (takeall n xs |> concat) = xs

Example:

  • (takeall 3 (1--10)) = [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]; [10]]
val splitwhile : ('a -> bool) -> 'a list -> 'a list * 'a list

(splitwhile p xs) is (a,b) where a is the longest prefix of xs of elements that satisfy p and b is the remaining suffix..

Invariant:

  • splitwhile p xs |> fun (a,b) -> a@b = xs
val takewhile : ('a -> bool) -> 'a list -> 'a list

(takewhile p) is (splitwhile p >> fst)

Invariant:

  • (takewhile p xs @ dropwhile p xs) = xs
val dropwhile : ('a -> bool) -> 'a list -> 'a list

(dropwhile p xs) is (splitwhile p >> snd).

Invariant:

  • ∀xs : ∀p : (takewhile p xs @ dropwhile p xs) = xs

Searching Lists

val mem : 'a -> 'a list -> bool

mem is List.mem.

val one_of : 'a list -> 'a -> bool

one_of is (flip List.mem).

val partition : ('a -> bool) -> 'a list -> 'a list * 'a list

partition is Lists.partition.

Zipping and Unzipping Lists

val zip : 'a list -> 'b list -> ('a * 'b) list

(zip xs ys) takes two lists and returns a list of corresponding pairs; tail-recursive.

This is the same as List.combine, except that if one input list is short, excess elements of the longer list are discarded, rather than raising an exception.

Examples:

  • (zip (1--4) (5--8)) = [(1, 5); (2, 6); (3, 7); (4, 8)]
  • (zip (1--2) (5--8)) = [(1, 5); (2, 6)]
val zipwith : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list

(zipwith f xs ys) is zip xs ys |> map (uncurry f).

val unzip : ('a * 'b) list -> 'a list * 'b list

(unzip xs) is List.split: it transforms a list of pairs into a list of first components and a list of second components.

Invariant:

  • (zip xs ys |> unzip) = (xs,ys) iff (len xs = len ys)

Association Lists

module Assoc = List.Assoc

Functions for working with association lists (alists).

Sorting and Such

See also on for a nice way to make comparison functions.

val sorted : ('a -> 'a -> int) -> 'a list -> bool

(sorted cmp list) is true iff (sort cmp list = list) and is false otherwise; O(n); tail-recursive, constant space.

sorted terminates at the first out-of-order value (if any), so it's much faster than (sort cmp list = list), especially for unsorted lists.

val uniq : ?compare:('a -> 'a -> int) -> 'a list -> 'a list

(uniq ?compare list) is the list of representative elements of the identical subsequences of xs; tail-recursive.

It's like sort_uniq but gives a different result for unsorted inputs.

Example:

  • (uniq [1;1;2;3;3;3;3;2;2;3;3]) = [1; 2; 3; 2; 3]

Invariant:

  • ∀xs : (sort compare xs |> uniq ~compare) = (sort_uniq compare xs)
  • parameter compare

    the comparison function (default: compare)

val uniqc : ?compare:('a -> 'a -> int) -> 'a list -> (int * 'a) list

(uniqc ?compare xs) is like (uniq xs) but each element is paired with the size of the original subsequence; tail-recursive.

Example:

  • (uniqc [1;1;2;3;3;3;3]) = [(2, 1); (1, 2); (4, 3)]
  • parameter compare

    the comparison function (default: compare)

Indexing and Projection

val index : ?z:int -> 'a list -> (int * 'a) list

(index ?z list) is an alist whose keys are successive integers (starting from z (default: 0) and whose values are the elements of list; tail-recursive.

Examples:

  • (index (1--4)) = [(0, 1); (1, 2); (2, 3); (3, 4)]
  • (index ~z:1 (1--4)) = [(1, 1); (2, 2); (3, 3); (4, 4)]
val pos : ?eq:('a -> 'a -> bool) -> 'a -> 'a list -> int

(pos x xs) is the position (index) of the first x in xs, or -1 if x is NOT in xs; tail-recursive.

val project : ?relaxed:bool -> int list -> 'a list -> 'a list

(project ?relaxed is xs) projects the elements of xs indexed by the indices in is; tail-recursive in the length of is.

The result is in the order of the occurrence of the indices in is.

If any index in is >= (len xs) or < 0, Not_found is raised, unless ~relaxed:true, in which case any bad indices are ignored, and the length of the result may be less than the length of is.

Examples:

  • (project [10] (1--20)) = [11]
  • (project [3;2;1;0] (1--4)) = [4; 3; 2; 1]
  • (project [4;4;4] (1--10)) = [5; 5; 5]

Invariants:

  • ((project ~relaxed:false is xs) |> len) = (len is)
  • ((project ~relaxed:false is []) && is <> []) = ⊥
  • (project ~relaxed:true is []) = []
  • (project [] xs) = []
  • ∀n . n < 1 let xs = 1--n in (project (map pred xs) xs) = xs
  • (project is xs) = (map (List.nth xs) is)
  • raises Not_found

    if not relaxed and any index >= (len xs) or < 0

Lists as Sets

Many of these functions are extremely inefficient compared to using Set. For use on lists guaranteed to be extremely short, or for playing in the top-level.

In most cases, in the spirit of "lists as sets", the order of elements is not preserved.

val nub : ?compare:('a -> 'a -> int) -> 'a list -> 'a list

(nub ?compare xs) is the list xs with equal elements removed; tail-recursive; O(n log n).

Equality is determined by compare (default: Stdlib.compare).

The order of the elements in xs is not preserved.

Runs in constant heap space (in addition to the size of the result list) and logarithmic stack space.

nub (1--5 @ 1--3 @ 4--6) = [1; 2; 3; 4; 5; 6]

val nub2 : ?compare:('a -> 'a -> int) -> 'a list -> 'a list

nub2 is nub but the order of the elements of the list is preserved; not tail-recursive; O(n^2).)

The 2 in nub2 is a reminder that it's O(n^2).

val union : ?compare:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list

(union ?compare xs ys) returns the list union of the two lists (with no duplicates); not tail-recursive (length of the first argument).

Equality is determined by compare (default: Stdlib.compare).

The order of the elements in xs and ys is not preserved.

  • (union xs ys) = (xs @ ys |> nub)
val intersect : ?compare:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list

(intersect ?compare xs ys) returns the list intersection of the two lists; tail-recursive; O(n^2).

Equality is determined by compare (default: Stdlib.compare).

The order of the elements in xs and ys is not preserved.

val subset : ?compare:('a -> 'a -> int) -> 'a list -> 'a list -> bool

(subset ?compare xs ys) is true if xs is a subset of ys; O(n^2).

Equality is determined by compare (default: Stdlib.compare).

The order of the elements in xs and ys is not preserved.

val diff : ?compare:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list

(diff ?compare xs ys): list difference: the elements of xs minus all of the elements in ys; tail-recursive, O(n^2).

Equality is determined by compare (default: Stdlib.compare).

The order of the elements in xs and ys is not preserved.

val cartesian_product : 'a list list -> 'a list list

(cartesian_product xss) is the Cartesian product of the list of lists xss; not tail-recursive.

Deck of cards:

(cartesian_product [["♠";"♥";"♦";"♣"];("A"::map string_of_int (2--10)@["J";"Q";"K"])])
val powerset : 'a list -> 'a list list

(powerset xs) is the list of all sublists of xs, including [] and xs itself; not tail-recursive.

val combinations : int -> 'a list -> 'a list list

(combinations n lst) is the list of all subset lists of lst consisting of n elements; not tail-recursive.

  • author Matt Teichman

List Iteration

val iter : ('a -> unit) -> 'a list -> unit

iter is iter.

val iteri : (int -> 'a -> unit) -> 'a list -> unit

iteri is iteri.

val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit

iter2 is iter2.

The List Monad

These functions can be used to hand-translate Haskell-style list comprehensions. For example:

[ (n,c) | n <- [1,2], c <- ['a','b'] ] = [(1, 'a'); (1, 'b'); (2, 'a'); (2, 'b')]

This can be expressed as:

[1;2] >>= fun n -> ['a';'b'] >>= fun c -> return (n,c)
val bind : 'a list -> ('a -> 'b list) -> 'b list

(bind list f) is (flatten (map f list)).

val return : 'a -> 'a list

(return n) is [n].

Ops

module Ops = List.Ops

Infix and prefix operators.

val assocs : 'a -> ('a * 'b) list -> 'b list

assocs is List.Assoc.assocs.

val (--) : int -> int -> int list

(--) is List.Ops.(--).

Non-Empty Lists

module List1 : sig ... end

Non-Empty Lists

Random

module Random : sig ... end

Additional random functions.

val shuffle : ?state:Random.State.t -> 'a list -> 'a list

shuffle is Random.shuffle.

val choose : ?state:Stdlib.Random.State.t -> ?n:int -> int -> 'a list -> 'a list

choose is Random.choose.

Hash Tables

module Hashtbl : sig ... end

This is Ocaml's standard Hashtbl with some additional functions.

Arrays

module Array : sig ... end

OCaml's Array module with some extra functions.

Immutable Arrays

module Ia = Ia

1-Based Arrays

module A1 = A1

OCaml's Array module with 1-based indexing.

Generators

module Gen : sig ... end

Trivial generators ("lazy" sequences / streams). NOT thread-safe.

Chars

module Chars : sig ... end

Additional char functions.

module Char : sig ... end

This is Ocaml's standard Char with the additional functions from Chars.

Format

module Format : sig ... end

This is Ocaml's standard Format with some additional functions and values.

Strings

module Strings : sig ... end

Additional string functions.

module String : sig ... end

This is Ocaml's standard String with the additional functions from Strings and with Strings.Ops opened.

val split : ?elide:bool -> ?complement:bool -> ?sep:string -> string -> string list

split is Strings.split

val join : ?elide:bool -> ?sep:string -> string list -> string

join is Strings.join

val (#!) : string -> int -> char

(#!) is Strings.(#!).

val (#.) : string -> (int * int) -> string

(#.) is Strings.(#.).

module AIString : sig ... end

Case-insensitive ASCII strings.

Show

module Show : sig ... end

Alternate access to Type-Specific string conversions.

Print

module Print : sig ... end

Alternate access to type-specific print functions.

Vectors

module type VECTOR = sig ... end

Fast functional arrays.

module Vector : VECTOR

See VECTOR.

Maps

module Map : sig ... end

Map.Make (M) is the module returned by OCaml's Map.Make (M) with some additional functions.

Sets

module Set : sig ... end

Set.Make (M) is the module returned by Stdlib.Set.Make (M) with some additional functions.

Multisets (aka bags)

module Multiset : sig ... end

Multiset.Make (Ord) is a set of Ord.t's with repetition.

Stacks

module type STACK = sig ... end

Purely functional stacks.

module Stack : STACK

See STACK.

Queues

module Queue : sig ... end

Purely functional FIFO queues.

module IQueue : sig ... end

The Standard Library's imperative queues.

Rose Trees

module Rose : sig ... end

N-ary (Rose) trees.

Leftist

module Leftist : sig ... end

A leftist heap; can be a min-heap or a max-heap.

System

val argv0 : string

argv0 is (Sys.argv.[0]) or else Sys.executable_name.

val argv : string list

argv is (Array.to_list Sys.argv |> List.tl), but is [] if (Sys.argv) = [||].

val syserrors : ?exit:bool -> ?message:(?ff:Format.formatter -> ?prefix:string -> string -> unit) -> ('a -> unit) -> 'a -> unit

(syserrors ?exit ?message f x) is (Sys.catch_break true; f x); any Sys_error or Unix.Unix_error exceptions are printed "more attractively" (via Exn.to_string) to stderr.

We call (Sys.catch_break true) because otherwise SIGINT (the signal sent by a control-C) terminates the program without allowing finalizers to finalize!

If (~exit = true), the program terminates via Stdlib.exit; otherwise, the program does not exit at all -- false is good for testing in the top-level (default value for ~exit: true).

Error messages are printed via ~message (default: Message.message). ~message will be called with various exit statuses for the following exceptions as follows:

"More attractively" means, for example, that an attempt to open a non-existent file would look like: /etc/passwdx: No such file or directory

rather than the usual OCaml:

 Fatal error: exception Sys_error("/etc/passwdx: No such file or directory")
Raised by primitive operation at unknown location
Called from unknown location

Typical usage:

let main () = iter (readfile $ write stdout) argv
let () = syserrors main ()
val version_of_string : string -> int Option.t list

version_of_string converts common version number strings to values that can be easily compared.

N.B. due to the variation in version number formats, one can't typically expect to meaningfully compare the versions of two different programs, but fortunately one can typically compare newer and older versions of the same program.

Examples:

  • (version_of_string "1.1.11+50+gb685338-1" = [Some 1; Some 1; Some 11; Some 50; None; Some 1])
  • (on (<) version_of_string "1.1.11+50+gb685338-1" "1.2.11+50+gb68531238-1")

Files

module File : sig ... end

Additional functions on files and filenames.

val (~~) : string -> string

(~~) is File.squiggle.

val withcd : (string -> 'a) -> string -> 'a

withcd is File.withcd.

Input / Output

Types

type eol =
  1. | CR
    (*

    '\r' is the EOL character (old Macintosh-style)

    *)
  2. | LF
    (*

    '\n' is the EOL character (Unix-style)

    *)
  3. | CRLF
    (*

    "\r\n" are the EOL characters (Windows-style)

    *)

The type of line-endings.

val eol : eol -> string

(eol e) returns the string corresponding to the line-ending.

Finalizers

Avoiding file descriptor leaks.

N.B. within and without do not perform ~-expansion on filenames; in typical use where filenames come from the command-line, this is unnecessary because the shell does the ~-expansion before your program sees the filename.

If you want to do ~-expansion yourself, just transform e.g.:

(within read) -> (within read << File.squiggle)

val iflags : Stdlib.open_flag list

iflags are the default flags passed to open_in_gen by within (default: [Open_rdonly]).

val oflags : Stdlib.open_flag list

oflags are the default flags passed to open_out_gen by without (default: [Open_creat;Open_wronly;Open_trunc]).

val dash : string

dash is the default filename that is interpreted as stdin or stdout by Prelude I/O functions.

The default is "-".

See: within, without, readfile, and writefile.

val within : ?dash:string option -> ?iflags:Stdlib.open_flag list -> (Stdlib.in_channel -> 'a) -> string -> 'a

(within ?dash ?iflags f file) opens file for input and returns (f c) where c is the in_channel; c is guaranteed to be closed when within returns, even if f raises an exception (which is re-raised).

iflags are passed to open_in_gen (default: iflags).

dash specifies a filename that is interpreted as stdin (default: Some dash); use ~dash:None to avoid any such interpretation.

val without : ?dash:string option -> ?oflags:Stdlib.open_flag list -> ?perm:int -> (Stdlib.out_channel -> 'a) -> string -> 'a

(without ?dash ?oflags ?perm f file) opens file for output and returns (f c) where c is the out_channel; c is guaranteed to be closed when without returns, even if f raises an exception (which is re-raised).

dash specifies a filename that is interpreted as stdout (default: Some dash); use ~dash:None to avoid any such interpretation.

oflags are passed to open_out_gen (default: oflags).

perm specifies the permissions used when a file is created (default: 0o666); these are subject to your umask in the usual manner.

val withinout : ?dash:string option -> ?iflags:Stdlib.open_flag list -> ?oflags:Stdlib.open_flag list -> ?perm:int -> (Stdlib.in_channel -> Stdlib.out_channel -> 'a) -> infile:string -> outfile:string -> 'a

(withinout ?dash ?iflags ?oflags ?perm f ~infile ~outfile) opens infile for input and outfile for output and returns (f inc outc) where inc is the in_channel and outc is the out_channel; both channels are guaranteed to be closed when withinout returns, even if f raises an exception (which is re-raised).

dash, perm, and oflags are as for without, and iflags is as for within.

val withtempfile : ?tmpdir:string -> ?oflags:Stdlib.open_flag list -> ?perm:int -> ?prefix:string -> ?suffix:string -> (string -> Stdlib.out_channel -> 'a) -> 'a

(withtempfile ?tmpdir ?oflags ?perm ?prefix ?suffix f) calls f with a secure, writable temporary file; when f returns, the temp file is guaranteed to be removed.

f is called with two parameters, the name of the temp file, and an output channel open on the temp file. f can close and reopen the file (say, for reading) if it likes.

Input

val blocksize : int

blocksize is the default block and buffer size for read and readblock.

val read : ?bufsize:int -> Stdlib.in_channel -> string

(read ?bufsize c) reads the entire contents of in_channel c and returns the result as a string.

bufsize is the size of the input buffer used (default: blocksize).

val readblock : ?buf:bytes -> ?size:int -> Stdlib.in_channel -> string Option.t

(readblock ?buf ?size c) returns (Some b) where b is the next block of size (or fewer) characters from channel c, or else None upon end of file.

If you are calling readblock repeatedly, as is typical, it is more efficient to pass ~buf, a Bytes.t of size >= size (this minimizes allocations).

size is the size of the input buffer used (default: Bytes.length buf or else blocksize).

val readfile : ?dash:string option -> ?bufsize:int -> string -> string

(readfile ?dash ?bufsize fn) is (within ?dash (read ?bufsize) fn).

val readline : Stdlib.in_channel -> string

readline is input_line.

val readline' : ?elide:bool -> ?eol:eol -> Stdlib.in_channel -> string

(readline' ?elide ?buf ?eol chan) is a readline that retains the EOL character(s).

Rationale:

  1. Precise handling of Mac and Windows files on Unix systems.
  2. Neither (foldlines ~readline:readline (fun () -> print_endline) ()) nor (foldlines ~readline:readline (fun () -> print_string) ()) is guaranteed to make an exact copy of their input, whereas (foldlines ~readline:readline' (fun () -> print_string) ()) is.

So: (writefile ~fn:"/tmp/foo" "foo\n"; within readline' "/tmp/foo" = "foo\n")

whereas: (writefile ~fn:"/tmp/foo" "foo\n"; within readline "/tmp/foo" = "foo")

~eol determines the EOL character(s). The default for ~eol is LF. In CRLF mode, isolated '\r' and '\n' do not terminate the line, and are returned "in the middle" of the line.

~elide:true causes the EOL character(s) to be trimmed from the end of the line, like readline always does for '\n'. The default value for ~elide is false.

Mnemonic: the ' in readline' stands for the presence of the EOL.

val readlines : ?readline:(Stdlib.in_channel -> string) -> Stdlib.in_channel -> string list

(readlines ?readline c) is a list of all the lines on the in_channel c; end-of-line characters will be present or absent depending the value you choose for ~readline; the default trims EOLs.

~readline is the function that reads each line; suitable candidates include input_line (the default), readline, and readline'.

val foldchars : ('a -> char -> 'a) -> 'a -> Stdlib.in_channel -> 'a

(foldchars f acc c) folds f over the chars on in_channel c.

(foldchars snoc [] >> rev >> String.implode = readfile), but would be considerably less efficient than readfile.

val foldlines : ?readline:(Stdlib.in_channel -> string) -> ('a -> string -> 'a) -> 'a -> Stdlib.in_channel -> 'a

(foldlines ?readline f acc c) folds f over the lines on in_channel c.

?readline is as for readlines.

(foldlines (snocwith f) [] >> rev) = maplines f
val maplines : ?readline:(Stdlib.in_channel -> string) -> (string -> 'a) -> Stdlib.in_channel -> 'a list

(maplines ?readline f c) maps f across all the lines on in_channel c, returning the list of results.

?readline is as for readlines.

val iterlines : ?readline:(Stdlib.in_channel -> string) -> (string -> unit) -> Stdlib.in_channel -> unit

(iterlines1 ?readline f c) applies f to each of the lines on in_channel c, for side-effect.

?readline is as for readlines.

val chars_of_chan : Stdlib.in_channel -> char Seq.t

(chars_of_chan chan) is the sequence of characters from chan.

val lines_of_chan : Stdlib.in_channel -> string Seq.t

(lines_of_chan chan) is the sequence of lines from chan.

Output

val print : string -> unit

print is print_endline.

val write : Stdlib.out_channel -> string -> unit

write is output_string.

val writeline : ?eol:eol -> Stdlib.out_channel -> string -> unit

(writeline ?eol chan s) is (output_string chan s) followed by the line-ending ~eol (default: LF).

val writelines : ?eol:eol -> Stdlib.out_channel -> string list -> unit

(writelines ?eol chan) is (iter (writeline ?eol chan))

val writefile : ?dash:string option -> ?oflags:Stdlib.open_flag list -> ?perm:int -> fn:string -> string -> unit

(writefile ?dash ?oflags ?perm ~fn s) writes s to file fn, passing the optional parameters to without.

val copyto : ?size:int -> Stdlib.out_channel -> Stdlib.in_channel -> unit

(copyto ?size oc ic) copies the contents of the input channel ic to the output channel oc one size-block at a time.

?size defaults to blocksize.

Examples:

  • print a file to standard output: (within (copyto stdout) "/etc/passwd")
  • copy "infile" to "outfile": (without (fun oc -> within (copyto oc) "infile") "outfile")
val copy : ?size:int -> ?oflags:Stdlib.open_flag list -> ?iflags:Stdlib.open_flag list -> ?perm:int -> infile:string -> outfile:string -> unit -> unit

(copy ?size ?oflags ?iflags ?perm ~infile ~outfile ()) copies the contents of the file infile to the file outfile.

?size is passed to copyto; ?oflags is passed to within; ?iflags and ?perm are passed to without.

Interactive

module Interact : sig ... end

Simple interaction with a human at a terminal.

Units

module Units : sig ... end

Modules for converting and displaying units.

Format Date and Time

Parsing and Formatting Date and Time

Including a pure OCaml implementation of strftime(3).

module Time : sig ... end

Messages

module Message : sig ... end

Easy to use message functions for warnings, errors, and verbosity, with a lot of fiddly options.

Logging

module Log : sig ... end

Simple functions for log files with timestamps, log rotation, etc.

Email

module Email : sig ... end

Parse (partially) Email mboxes and messages.

Refer Data

module Refer : sig ... end

Parse and generate Extended Refer databases.

Macros

module Macro : sig ... end

Simple macro expansion in strings.

International Standard Numbers

module ISN : sig ... end

Unix

module Unix : sig ... end

Additional Unix functions.

Prerequisites

module Prereq : sig ... end

Functions to test for the availability of external prerequisite commands.

Extensions

Extensions to modules we don't want to depend upon.

module Extended : sig ... end

Extensions.

Example

Here's a quick example to give you an idea of what things looks like. This program isn't intended to be necessarily the most readable, or the most terse, but rather to illustrate as many Prelude features as possible in a small amount of code.

I've added line numbers; see below for a line-by-line explanation.

This program reads the file named as its first command-line argument, or, if there is no such argument, the file /usr/share/dict/words as a default. It splits each line into whitespace-separated words, and adds each word to a multiset (bag) which gathers together strings case-insensitively. Then it prints, in case-insensitive alphabetical order, all the words that have more than one spelling. The output looks something like this:

2: [blackberry's; BlackBerry's]
2: [cordilleras; Cordilleras]
2: [debs; Debs]
2: [dot's; Dot's]
3: [ms; Ms; MS]
3: [teleprompter; TelePrompter; TelePrompTer]

A brief error message (no stack trace) is printed if there's a problem opening a named file, in which case the program exits with status 125. The error message might look like this:

 1 open Prelude
 2 module MS = Multiset.Make (AIString)
 3 let main () =
 4   argv
 5   |> head
 6   |> Option.default "/usr/share/dict/words"
 7   |> within (foldlines (fun ms -> split >> foldr MS.add ms) MS.empty)
 8   |> flip (MS.fold (conswhen (len >> gt 1))) []
 9   |> rev
10   |> iter (fun ws -> to_string id ws |> printf "%d: %s\n" (len ws))
11 let () = syserrors main ()

Explanation

  1. Opening Prelude is the intended usage.
  2. We'll use a Multiset to group together equivalent strings; the AIString module implements OrderedType for ASCII case-Insensitive strings.
  3. Define a main function.
  4. Get the command-line arguments (excluding argv0) as a list.
  5. Take the first arg (as a string option).
  6. If it's None (because argv is empty) replace it with "/usr/share/dict/words".
  7. Feed the filename to within (...) to be opened, and passed as an in_channel to the function -- and guaranteed to be closed when the function terminates, even if an exception was raised. The function (see below) returns a Multiset.S.t of all the words in the file.
  8. Now we fold over the Multiset and return a list of the equivalent words, as a string list list. Each sublist is the different spellings of a word.
  9. Because we consed-up the list, we reverse it to get alphabetical order.
  10. Now we print each sublist in a notation similar to the way the top-level prints a list.
  11. Finally we call our main, catching any exceptions (we only expect I/O errors) and printing them attractively, with no stack trace.

Line 7:

foldlines (fun ms -> split >> foldr MS.add ms) MS.empty

This function adds all the words of the input to our multiset. foldlines folds a flipped-cons-like function over the lines of an in_channel. MS.empty is our initial accumulator. Our function uses split to split the line into words (a string list) and we fold over that list with foldr, which is a synonym for List.fold_right. MS.add adds a word to our multiset. (>>) is left-to-right function composition.

Line 8:

flip (MS.fold (conswhen (len >> gt 1))) []

This function folds over the equivalence-classes of word-spellings that make up our multiset. The multiset stores each equivalence-class as a list of strings that are equal according to AIString.compare.

(len >> gt 1) is a predicate that's true iff a word-list has length greater than 1 -- in other words, if the word has multiple spellings. len is List.length and gt is (flip (>)).

conswhen is a (::) that only conses when it's predicate is true. So (MS.fold (conswhen (len >> gt 1))) is a function that takes a multiset and an initial accumulator (the empty list []) and conses an equivalence-class onto the accumulator if it has multiple spellings. The order of that function's two parameters is awkward so we flip them (and avoid writing a lambda). The result of this whole function is a list of lists: a list of non-trivial equivalence-classes.

Line 10:

iter (fun ws -> to_string id ws |> printf "%d: %s\n" (len ws))

Finally we iterate over the list of equivalence-classes and print each list on a line, prefixed by its length. iter is List.iter. Prelude does (include Printf) since its functions are so useful and have unambiguous names. Since Prelude does (include Prelude.Lists), to_string is Lists.to_string. Prelude defines a flexible to_string function for all its data types and for most of the OCaml base types. to_string takes a function to convert a list element to a string -- since we have a list of strings, we just use id, the identity function. Lists.to_string takes a number of optional parameters but it's default is to format a list the way the top-level would.