天津Java培训
达内天津天大中心

022-87670409

热门课程

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

  • 时间:2016-04-19
  • 发布:天津达内
  • 来源:天津达内

  曾经上学的时候我们总是会抱怨我们学数据学那么多以后会都用到吗?天津java培训就来讲解一个关于数据与程序转化的案例。 这是一篇将离散数学结构中的集合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的元素。
集合作为类型
将数学转换成代码案例(Java Racket Haskell和Python)
无穷大集合往往被编码成类型,当然一些有限大集合也会编码成类型。一个集合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 {
public boolean isLessThan(T that) ;
}
abstract class SortedSet> {
public abstract boolean isEmpty() ;
public abstract boolean contains(T element) ;
public abstract SortedSet add(T element) ;
public static final > SortedSet empty() {
return new EmptySet();
}
}
final class EmptySet> extends SortedSet {
public boolean isEmpty() {
return true ;
}
public boolean contains(T element) {
return false ;
}
public SortedSet add(T element) {
return new Node(this,element,this) ;
}
public EmptySet() {
}
}
final class Node> extends SortedSet {
private final SortedSet left ;
private final T element ;
private final SortedSet right ;
public boolean isEmpty() {
return false ;
}
public Node(SortedSet left, T element, SortedSet 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 add(T newGuy) {
if (newGuy.isLessThan(this.element)) {
return new Node(left.add(newGuy),this.element,right) ;
} else if (this.element.isLessThan(newGuy)) {
return new Node(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
句法集在形式化方法和编程语言领域中是常见的。
天津java培训小编也终于知道为什么大学要学高数,还要学习微积分,难道就是为了我在编程序的时候使用吗?
让编程变得可推导的三种方向
让程序变得可推导,关键是对可变状态的围剿,纵观业界有三种方向现在就来为大家分享一下这些内容吧!
1. 通过函数式语言让不变性成为语言的默认特性,这样可变状态变成特例。这种方式会让程序员尽量不用可变状态,就是没办法回避也会努力花力气做好做完善。
2.让可变状态变成编程的核心,也就是说,从需求分析到代码设计,可变状态一直是我们的核心,重点对象,包含可变状态的DDD实体方法属于这种范畴。参考:通过实体快照实现事件建模
3.通过关注分离,将可变状态从系统中通过特殊框架和模式分离出来,比如Javascript世界的React.js,包括Actor模型倡导的reactive编程方式,所谓react即时反应,隐式其实隐藏着一个前提,在状态变化触发的即时反应,所以,这种方法也是一种以可变状态为核心的。
javascript前端React.js相关参考:前端Flux架构简介,最新的英文youtube视频:React.js Conf 2015 Keynote - Introducing React Native
天津java培训小编和大家讲的内容希望大家以后都多多关注一点,很多内容都会关乎到自己发展的选择,因此好好努力吧!
转自: 你的编程语言可推导(Reasonable)吗?
上一篇:Go语言走向企业应用还需要什么?
下一篇:“因材施教,分级培优”十问十答
选择城市和中心
贵州省

广西省

海南省