Caution: Math has no side effects
The fatal mistake newcomers make when translating math into code is using mutable data structures where only an immutable structure was correct.
Mathematics has no side effects.
Math cannot modify the value of a variable--either global or local. It cannot mutate an element in an array. And, a mathematical function always returns the same value for the same input.
The literal rendering of mathematics into code cannot contain side effects.
Mathematics is a purely functional language.
Of course, once the constraints on an implementation are understood, it's usually possible to exchange immutable data structures for mutable ones in key places to achieve performance savings.
But, for the purposes of prototyping, it's always best to start with a direct, purely functional implementation.
Sets and power sets
The rendering of a set as code will usually be a type; a collection backed by a balanced tree or a hash map; or a predicate.
In mathematics, a set is an unordered collection of elements.
The empty set--∅--is a special set containing no elements.
The syntax for literal sets is curly braces: {}. For example, the set {1,2,3} is the set containing 1, 2 and 3.
The relationship x ∈ S declares that the value x is a member of the set S.
Sets as types
Infinite sets tend to be encoded as types.
(Of course, some finite sets are encoded as types too.)
In some cases, a set X is defined as a subset of another set Y:
X ⊂ Y.
This subset relationship could be represented as inheritence in a language like Java or Python, if these sets are meant to be types:
class X extends Y { ... }
When a set X is defined to be the power set of another set Y:
then X and Y will be types, and members of X will be collections.
Sets as collections
When a set's contents are computed at run-time, then it will often be asorted collection backed by a structure like a red-black tree.
[See my post on purely functional red-black trees including deletion.]
It's not hard to implement a purely functional, sorted (but unbalanced) search tree in Java:
interface Ordered <T> {
public boolean isLessThan(T that) ;
}
abstract class SortedSet<T extends Ordered<T>> {
public abstract boolean isEmpty() ;
public abstract boolean contains(T element) ;
public abstract SortedSet<T> add(T element) ;
public static final <E extends Ordered<E>> SortedSet<E> empty() {
return new EmptySet<E>();
}
}
final class EmptySet<T extends Ordered<T>> extends SortedSet<T> {
public boolean isEmpty() {
return true ;
}
public boolean contains(T element) {
return false ;
}
public SortedSet<T> add(T element) {
return new Node<T>(this,element,this) ;
}
public EmptySet() {
}
}
final class Node<T extends Ordered<T>> extends SortedSet<T> {
private final SortedSet<T> left ;
private final T element ;
private final SortedSet<T> right ;
public boolean isEmpty() {
return false ;
}
public Node(SortedSet<T> left, T element, SortedSet<T> right) {
this.left = left ;
this.right = right ;
this.element = element ;
}
public boolean contains(T needle) {
if (needle.isLessThan(this.element)) {
return this.left.contains(needle) ;
} else if (this.element.isLessThan(needle)) {
return this.right.contains(needle) ;
} else {
return true ;
}
}
public SortedSet<T> add(T newGuy) {
if (newGuy.isLessThan(this.element)) {
return new Node<T>(left.add(newGuy),this.element,right) ;
} else if (this.element.isLessThan(newGuy)) {
return new Node<T>(left,this.element,right.add(newGuy)) ;
} else {
return this ; // Already in set.
}
}
}
Be warned that the Java library's Set interface (optionally) allows imperative addition and removal of elements. A computational rendering of mathematics cannot use these features.
A run-time set might also be backed by an immutable hash table.
Regardless of representation, these set data structures typically need to support operations like enumeration, union, intersection and difference, and relations like membership, equality and subset.
Whether a balanced tree or a hash map is better for ease of implementation and performance rests on type of the elements in the set and the algorithmic uses-cases for the set operations.
In some cases, it's easy to provide an efficient ordering function. Sometimes, it's easier to provide a hash function and a definition of equality.
Python provides syntactic support for hash-backed sets:
>>> { 3 , 2 , 1 } == { 1 , 2 , 3 }
True
>>> {1,2,3} | {3,4,5}
set([1, 2, 3, 4, 5])
Racket also provides native sets:
> (equal? (set 3 2 1) (set 1 2 3)) #t > (set-union (set 3 2 1) (set 3 4 5)) (set 1 2 3 4 5)
In Haskell, Data.Set provides a full-featured implementation of sorted, balanced tree-backed sets.
I'm fond of the following notation for Haskell:
import Data.Set type P = Data.Set.Set
so that I can write things like:
type Ints = P(Int)
which is aesthetically closer to the formal mathematics.
Sets as predicates
If the set X is a subset of Y, but the structure of the set X is outside the descriptive capacity of the type system, then X could be represented as a predicate:
class Y {
public boolean isX() { ... }
}
or in Haskell:isX :: Y -> Bool
Some advanced programming languages like Agda support dependent types, which allow predicates in the type system itself.
In Racket, rich, expressive contracts take the place of dependent types.
Disjoint union (sums)
A disjoint (or tagged) union of several sets is a new set containing all of the elements of the constituent sets, but with an implicit mark (or tag) added to each element to indicate from which constitutent set it came.
The set A + B is the disjoint union of the sets A and B.
In mathematics, that distinguishing mark is almost always kept implicit or inferred from context. (The tag is rarely needed.)
In fact, when that mark is required, it is common to use syntactic sets.
In Java (and other object-oriented languages), sum types are represented through class-based inheritence. The sum forms an abstract base type, and each constituent forms a subtype. For example, the type A + B + C would become:
abstract class ApBpC { ... }
class A extends ApBpC { ... }
class B extends ApBpC { ... }
class C extends ApBpC { ... }
Haskell supports algebraic data types that closely mimic the sum form. Explicit constructors serve as tags. For example:
data ApBpC = ACons A
| BCons B
| CCons C
The constructors are also used for pattern-matching; for example:
whatAmI (ACons _) = "I'm an A." whatAmI (BCons _) = "I'm a B." whatAmI (CCons _) = "I'm a C."
Of course, in Java, a whatAmI method becomes dynamic dispatch:
abstract class ApBpC {
abstract public String whatAmI() ;
}
class A extends ApBpC {
public String whatAmI() {
return "I'm an A." ;
}
}
class B extends ApBpC {
public String whatAmI() {
return "I'm a B." ;
}
}
class C extends ApBpC {
public String whatAmI() {
return "I'm a C." ;
}
}
In untyped languages like Racket, where the universal type is already the sum of all types, there is no need for a special embedding.
Languages like Python can exploit class-based inheritance or take the Racket-like approach for representing sum types.
Sequences and vectors
Sequences are a common discrete structure, and their rendering in code is perhaps the most straightforward.
In formal notation, the set of sequences over elements in S is written S*.
It is usually clear from context whether S* should contain infinite sequences or only finite ones. (And, in many cases, it doesn't matter.)
For example, if the set A = {a, b} is an alphabet, then the set of strings over this alphabet is A*, which would contain elements like ab and babba.
If the variable used to denote elements of the set S is s, then a sequence in the set S* is usually a bold-faced s or s. (It is a common convention to use the lower-case version of a set to denote members of that set.)
Given a sequence s, its first element is s1, and its ith element is si.
Explicit sequences tend to be wrapped in angle-brackets, so that:
(Please note that in LaTeX, one should use \langle and \rangle for angle brackets--not less than and greater than.)
Sequences as linked lists
Most frequently, a finite sequence will be encoded as a linked list.
For example, in Java:
abstract class Sequence<S> {
public abstract S getHead() ;
public abstract Sequence<S> getTail() ;
public abstract boolean isEmpty() ;
public static final <T> Sequence<T> cons(T head, Sequence<T> tail) {
return new Cons<T>(head,tail) ;
}
public static final <T> Sequence<T> nil() {
return new Nil<T>() ;
}
}
final class Cons<S> extends Sequence<S> {
private final S head ;
private final Sequence<S> tail ;
public S getHead() {
return this.head ;
}
public Sequence<S> getTail() {
return this.tail ;
}
public boolean isEmpty() {
return false ;
}
public Cons(S head, Sequence<S> tail) {
this.head = head ;
this.tail = tail ;
}
}
final class Nil<S> extends Sequence<S> {
public S getHead() {
throw new EmptySequenceException() ;
}
public Sequence<S> getTail() {
throw new EmptySequenceException() ;
}
public boolean isEmpty() {
return true ;
}
public Nil() { }
}
class EmptySequenceException extends RuntimeException {
}
class Test {
public static void main(String[] args) {
Sequence<Integer> end = Sequence.nil() ;
Sequence<Integer> si =
Sequence.cons(3, end) ;
}
}
Functional languages excel at encoding sequences. Haskell has a list type: []. A function that adds one to every element of a list could be written:
add1 :: [Int] -> [Int] add1 [] = [] add1 (hd:tl) = (hd + 1):(add1 tl)
Or, more succinctly using map:
add1 :: [Int] -> [Int] add1 = map (+1)
In most Lisps (like Racket), cons constructs lists, while car and cdr destruct:
(car (cons 1 (cons 2 '()))) == 1 (car (cdr (cons 1 (cons 2 '())))) == 2 (pair? '()) == #f (pair? (cons 1 '())) == #t
In Python, tuples and lists work about equally well as sequences, but tuples might be less error-prone since they're immutable.
Of course, the standard warning about side effects applies: do not use the side-effecting features of Python lists like popping an element.
Vectors as arrays
When dealing with a set of sequences which all have the same length, the term vector is commonly used instead of sequence.
The set of vectors over the set S of length n is written Sn.
Sometimes vectors are written with a right-arrow (→) over the unbolded representative variable.
Vectors can be efficiently encoded using arrays, but lists also suffice.
Remember: the array must not be mutated!
If you need to update an index in a vector, it should be copied into a new array first, leaving the original array untouched.
That said, it is often the case that you can prove that when one vector is computed as the update of another vector that the original vector is garbage. In these cases, it is a safe and common optimization to mutate the array.
Infinite sequences as streams
Infinite sequences are not common, but when they arise, they are often encoded as streams.
In Haskell, laziness means that any list can be an infinite list.
It is easy to encode an infinite sequence like the list of all natural numbers:
nats = 1:(map (+1) nats)
so that take 5 nats yields [1,2,3,4,5].
and, even more remarkably, we can filter this list to produce the list of all primes:
isPrime n = all (\ m -> n `mod` m /= 0) [2..n-1] primes = filter isPrime (tail nats)
It is actually the case that take 6 primes yields [2,3,5,7,11,13].
Racket includes a stream library, allowing the equivalent:
(define (inc n) (+ 1 n))
(define nats (stream-cons 1 (stream-map inc nats)))
(define (prime? n)
(call/ec (λ (return)
(for ([m (in-range 2 (- n 1))])
(when (= (modulo n m) 0)
(return #f)))
(return #t))))
(define primes (stream-filter prime? (stream-rest nats)))
In an object-oriented setting like Python or Java, streams can be constructed from an interface:
interface Stream<A> {
public A first() ;
public Stream<A> rest() ;
}
The first() method should be sure to cache its result, and if the stream is I/O-backed, then the rest() method should invoke the first() method.
Cartesian products (tuples)
Cartesian products, or tuples, are ordered collections, where the location of the element in the collection determines its type.
Cartesian products map onto records, structs and objects, with each index into the tuple occupying a field.
For instance, A × B produces a set of pairs, where the first element is from the set A, and the second is from the set B.
Individual tuples are denoted with parentheses.
For example, (a, b, c) is a member of A × B × C.
In Java, the type A × B would be a class:
class AtimesB {
public final A a ;
public final B b ;
public AtimesB(A a, B b) {
this.a = a ;
this.b = b ;
}
}
In Racket, this would be a struct:
(define-struct a×b (a b))
Python contains native tuple support:
>>> x = (1,1,2,3) >>> x[3] 3
But, one might just as easily have defined a class:
class MyTuple:
def __init__(self,first,second,third,fourth):
self.first = first ;
self.second = second ;
self.third = third ;
self.fourth = fourth ;
Haskell provides native tuple support too:
Prelude> let t = (1,2,3) Prelude> t (1,2,3)
Haskell also allows for record-like data types, such as in the following two definitions:
data AB = Pair A B
data AB' = Pair' { a :: A, b :: B }
Both definitions introduce constructors:
Pair :: A -> B -> AB Pair' :: A -> B -> AB'
The second definition introduces two extractors, one for each field:
a :: AB' -> A b :: AB' -> B
Functions (maps)
Mathematical functions transform inputs to outputs.
The set of functions from the set A into the set B is the set A → B.
Under the interpretation of (→) as an operator on sets, the signature:
can be interpreted as the function f is a member of the set X → Y:
In mathematical notation, there are several extant notations for application:
All of these are the application of the function f to the value x.
In code, functions can translate into procedures and methods, but if they're finite, they can also translate into finite maps backed by hash tables or sorted, balanced tree maps.
Fuctions as code
Most of the time a mathematical function will map into a procedure in the underlying language.
When a function is supposed to map into executable code, it's usually straightforward to make the mapping using the data structures and algorithms presented elsewhere in this guide.
Functions as maps
In some cases, mathematicians use functions as the formal analog of a hash table or a dictionary. For example:
represents a function identical to f except that x maps to y.
Please note that extending a function like this does not (and cannot) change the original function f!
Immutable red-black tree map are a great data structure for representing these finite functions meant to be extended.
Once again, it is not safe to use the mutable sorted maps and hash tables provided by the Java library, or the mutable dictionaries provided by Python.
Haskell provides the Data.Map library for this purpose, and Racket also offers immutable hash maps.
Sometimes, it is acceptable to hijack the native notion of functions to get them to act like immutable dictionaries. For instance, in Python, we can define extend:
def extend (f, x, y):
return lambda xx: y if xx == x else f(xx)
def empty(x): raise Exception("No such input")
so that the following works:
g = extend(extend(empty, 3, 4), 5, 6) print(g(3)) # prints 4 print(g(5)) # prints 6
The disadvantage of taking over the internal notion of function like this is that one cannot enumerate the contents of the function, as with a hash or tree-backed formulation.
Immutable maps atop mutable structures
If a language already provides a good native map-like structure (like Python's dictionaries), then it is possible to exploit this structure through shallow copies every time the map is extended:
class DictMap:
def __init__(self, contents):
self.contents = contents
def extend(self,x,y):
contents_ = copy.copy(self.contents)
contents_[x] = y
return DictMap(contents_)
def __call__(self,x):
return self.contents[x]
Relations
Structurally, a relation R is a (possibly infinite) set of subset of some Cartesian product.
The set of all relations over A × B is P(A × B).
Computational encodings of relations center around understanding relations in terms of other data structures.
In the special case where a relation relates elements of the same set, e.g. R ⊆A × A, then R defines a directed graph over nodes in A.
Given a relation R, the notation:
is equivalent to:
There are three common ways to encode a relation computationally: as a collection, as a function and as a predicate.
Relations as collections
Structurally, a relation is a set of tuples, and for finite relations, an encoding as a set of tuples is reasonable.
Relations as functions
Given a relation R ⊆ A × B, the following congruences allow a relation to be represented as a function:
This functional encoding of a relation is particularly popular for implementing the transition relation of abstract machines, which relates a machine state to all of its possible successors.
Relations as predicates
If one only needs to know whether or not some tuple is within the relation, then it is frequently most efficient to encode the relation as a predicate.
This view is supported by another congruence:
Syntax
Syntactic sets are common within the fields of formal methods and programming languages.
A syntactic definition for the set E uses the following form:
where each syntactic pattern pat defines a new syntactic form for constructing members of the set E.
A syntactic set is, in essence, a disjoint union with explicit tags.
Viewing syntactic sets as sum types guides translation into code.
Syntactic set examples
For example, we can define a syntax for expression trees:
| E | ::= | e + e |
e * e | ||
| n |
We might then define an evaluator eval : E → N on this set:
eval(e + e) | = eval(e) + eval(e) |
eval(e * e) | = eval(e) × eval(e) |
| eval(n) | = n |
In Java (or any object-oriented language), this could become:
abstract class Exp {
abstract public int eval() ;
}
class Sum extends Exp {
public final Exp left ;
public final Exp right ;
public Sum(Exp left, Exp right) {
this.left = left ;
this.right = right ;
}
public int eval() {
return left.eval() + right.eval() ;
}
}
class Product extends Exp {
public final Exp left ;
public final Exp right ;
public Product(Exp left, Exp right) {
this.left = left ;
this.right = right ;
}
public int eval() {
return left.eval() * right.eval() ;
}
}
class Const extends Exp {
public int value ;
public Const(int value) {
this.value = value ;
}
public int eval() {
return value ;
}
}
To define a sum type with explicit tags, one might use the following form:
| Kont | ::= | letk(v, e, Ï, κ) |
| seqk(e, Ï, κ) | ||
| setk(v,e, Ï, κ) | ||
| halt |
In Haskell, this structure could be:
data Kont = LetK Var Exp Env Kont
| SeqK Exp Env Kont
| SetK Var Exp Env Kont
| Halt
In mathematics, the syntactic notation can only be used if the representative variables for each set (e.g. κ for Kont, Ï for Env) have been clearly established, since in the Haskell notation, these types are required.
More resources
Chris Okasaki's Purely Functional Data Structures
For a lengthy example, my post on the CEK machine shows how to encode a nontrivial discrete structure---an abstract machine for the lambda calculus---in Haskell.
Source:http://matt.might.net/articles/discrete-math-and-code/
