将数学转换成代码案例(Java Racket Haskell和Python)

这是一篇将离散数学结构中的集合set，序列sequence，函数function，disjoint unuin，关系relation和语法转变成使用Java，Python，Racket和Haskell可运行的代码：

Translating mathematics into code: Examples in Jav

请注意：数学没有副作用
新手转换时最容易犯的错误就是使用将数学转变成使用可变数据结构的代码，实际应该是不可变数据结构才是正确的。

因为数学没有副作用(边际影响)。

数序不能修改变量的值，无论是本地还是全局，它不能将单个元素变成一个数组，数学函数对于相同输入总是输出同样的值。

数学转变成代码也不能包含副作用。

数学是真正纯函数语言。

当然，一旦这种约束理解了，也有可能使用可变数据结构替换不变数据结构，前提是为了提高性能。

但是原始目标不能忘记，开始时最好使用不可变数据结构。

集合Set
集合渲染(转换)成代码通常是一个类型type；一个集合背后是一个平衡树或一个Hasmap，或一个谓词predicate。

在数学中，一个集合是一个没有排序的元素集合。空集合代码包含没有任何元素的特殊集合。

集合的字符语法是大括号：{}，比如集合{1,2,3}是一个包含1 2和3元素的集合。 x ∈ S 关系定义了x的值是集合S的元素。

集合作为类型
无穷大集合往往被编码成类型，当然一些有限大集合也会编码成类型。一个集合X属于另外一个集合Y的子集：
X ⊂ Y

子集关系能够在Java或Python语言中表达为继承，当然，如果这些集合对应着类型的话：
class X extends Y { ... }

当一个集合X被定义另外一个power set(势集，幂集合)Y:
X = P(Y) = 2Y (注：Y在2的左上角，没有数学符号支持显示)
那么X和Y将是类型，而X的成员将是collection集合。

Set作为Collection
当一个Set的内容是在运行时计算的，那么其通常是一个排序的collection，背后是一red-black树之类数据结构支持。

使用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.
}
}
}

注意，Java库Set接口是允许对集合增加和删除元素的，但是作为数学的计算转换是不能使用这些特性的。

一个运行中的set也可以使用不可变hash table支持实现。

无论表现形式如何，这些set数据结构通常需要一些操作支持：如enumeration, union, intersection 和difference，像成员关系一样的关系，等同和子集等；

无论是一个平衡树还是一个Has map都是Set实现，主要结合性能考虑和具体算法使用场景。

Python提供了哈希支持set的语法实现：


>>> { 3 , 2 , 1 } == { 1 , 2 , 3 }
True

>>> {1,2,3} | {3,4,5}
set([1, 2, 3, 4, 5])

Haskell的Data.Set提供完整的排序平衡树的实现：


import Data.Set
type P = Data.Set.Set
type Ints = P(Int)

这在美学上更接近数学了。

Set作为谓词
如果set X是Y的子集，但是set X的结构又在类型系统的描述能力之外，那么，X应该被表达为谓语predicate：

class Y {
public boolean isX() { ... }
}

在Haskell:

isX :: Y -> Bool

一些先进的编程语言如Agda支持dependent依赖类型，允许谓词使用类型系统自身来表达。

(以下有删减，完整参考原文)
Disjoint union不相交并(求和)
set A+B是setA和B的Disjoint union；在java或其他面向对象语言中，求和类型是通过基于类的基础表达的，比如类型A+B+C将是：


abstract class ApBpC { ... }

class A extends ApBpC { ... }
class B extends ApBpC { ... }
class C extends ApBpC { ... }

Haskell使用代数数据类型，能模仿求和sum形式：


data ApBpC = ACons A
           | BCons B
           | CCons C

构造器可以使用模式匹配：


whatAmI (ACons _) = "I'm an A."
whatAmI (BCons _) = "I'm a B."
whatAmI (CCons _) = "I'm a C."

当然，在Java中，whatAmI方法称为动态分发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." ;
  }
}

Sequences as linked lists
....

Vectors as arrays
....

Infinite sequences as streams
....

Cartesian products (tuples) 笛卡尔乘积（元组）
笛卡儿乘积或元组是有序集合collection，元素在collection中所在位置决定了它的类型。

笛卡儿乘积可以映射到记录结构struct和对象，每个所在的索引占其一个字段；

....

函数(map)
数学上的函数是将输入转为输出；
函数的set是将set A转为set B，也就是A → B
箭头解释符号( →)是基set的操作。

f : X → Y可以被解释为函数f是集合set X → Y的成员:
f ∈ X → Y

对应几个数学符号为：
f(x) = f x = f.x

所有这些都是函数f对值x的应用。

在代码中，函数能够被转换为过程procedure和方法，但是如果它们是有限的，它们能转为有限map，其背后使用hastable或排序平衡树map支持

函数转换为过程procedure和方法这是很常见的。下面看看函数作为map：

f[x ↦ y]代表除了x映射到y以外与f相同的函数。请注意，拓展函数并不能改变原始函数f。

Immutable red-black tree map 是能表达这些被扩展的有限函数的数据结构。

使用Java库包提供的可变的排序map和hashtable是不安全的，包括Python提供的可变字典。

Haskell提供Data.Map库包来支持不可变的map；

....

关系
一个关系R(可能是无限)是一些笛卡尔乘积的子集的set。A × B 的关系集合set是 P(A × B)

关系可以表达为Collection；关系也可表达为函数；关系可作为谓语。

Syntax
句法集在形式化方法和编程语言领域中是常见的。
....