[ML] datatype 举例，二叉树

win_hate

SICP 的第二章陈述了这样的观点：数据可以看成一组建构函数和选择函数。较新一些的函式语言对此有内建的支持，即把建构函数和选择函数标准化了。以 ML 为例，它的 datatype 可以构建新的类型，支持多态和递归。在 scheme，选择函数通常要作一系列的判断后，才能从数据中挑出所需部分。ML为此提供了模式匹配。从本质上看，模式匹配跟分情处理没有区别。但模式匹配显然更清晰，用起来也轻松得多。

win_hate

用 datatype 声明一个二叉树类型：

1. 
   
2. datatype 'a tree = LEAF | NODE of 'a * 'a tree * 'a tree;
   

复制代码

二叉树的节点可以分内、外两种。外部的称为叶子，内部的有左右分支。上面的数据声明跟二叉树的原始定义几乎是一样的。

声明中的 'a 是所谓的类型变量。使用类型变量后，我们定义的树的节点内容可以为整数，也可以为字符串，也可以是其它类型。具体要在建构树的时候才确定下来。ML 的类型变量的记号为 ' 起头加个字母，比如 'a, 'b, 'c ...

LEAF, NODE 称为 tree 类型的值建构子。可以用它们来建构具体的二叉树。

如果只有一个叶子，不足以把 'a 确定下来

1. 
   
2. - val x=LEAF;
   
3. > val 'a x = LEAF : 'a tree
   

复制代码

可以自行设定 'a 的类型，下面的 x 是个整数叶子

1. 
   
2. - val x=LEAF:(int tree);
   
3. > val x = LEAF : int tree
   

复制代码

含有一个节点的二叉树，'a 的类型可以从节点的内容(13) 自动推导出来。

1. 
   
2. - val y = NODE(13, LEAF, LEAF);
   
3. > val y = NODE(13, LEAF, LEAF) : int tree
   

复制代码

一棵字符串树

1. 
   
2. - val y = NODE("SML", LEAF, LEAF);
   
3. > val y = NODE("SML", LEAF, LEAF) : string tree
   

复制代码

win_hate

建构出一棵二叉树后，如何解构它呢？ ML 对此的回答是模式匹配。

给定一棵二叉树：

1. 
   
2. val mytree =
   
3.     NODE ("This", NODE ("is", LEAF,
   
4.                            NODE ("a", NODE ("tree", LEAF, LEAF),
   
5.                                LEAF)),
   
6.         LEAF);
   

复制代码

我们来写一个前根序遍历:

• 叶子返回空；
• 内部节点返回：节点内容，左子树前根序序列，右子树前根序序列。
  

1. 
   
2. fun preorder LEAF = []
   
3.   | preorder (NODE(e, x, y)) = e::preorder (x)@preorder (y);
   

复制代码

fun 就是函数，这个是不是很 funny? 前面的建构子在这里用作模式匹配。

• preorder LEAF, 如果输入值是个叶子
• preorder (NODE(e, x, y))，如果输入值是个内部节点，起内容为 e，左右子树分别为 x, y
• :: 是列表插入
• @ 是列表的 append.
  

整个函数跟二叉树的前根序遍历算法完全一致，几乎没有多余的东西。

看看效果：

1. 
   
2. - preorder mytree;
   
3. > val it = ["This", "is", "a", "tree"] : string list
   

复制代码

把中根序和后根序补上，也是轻而易举。

1. 
   
2. fun inorder LEAF = []
   
3. | inorder (NODE(e,x,y))=inorder(x)@ e::inorder(y);
   
4. 
   
5. fun postorder LEAF = []
   
6.   | postorder (NODE (e, x, y)) = postorder(x)@postorder(y)@[e]
   

复制代码

MMMIX

原帖由 win_hate 于 2008-11-5 09:11 发表
SICP 的第二章陈述了这样的观点：数据可以看成一组建构函数和选择函数。较新一些的函式语言对此有内建的支持，即把建构函数和选择函数标准化了。以 ML 为例，它的 datatype 可以构建新的类型，支持多态和递归。  

这些 Haskell 也有支持，语法和 ML 也差不多，而且 Haskell 还能自动生成选择函数。

win_hate

前面的 preorder, inorder, 和 postorder 的确很简明，但效率是有问题的。问题出在 @  上。 x @ y 要遍历 x，这本来是可以避免的。下面是改进后的版本，可读性略为降低。

1. 
   
2. fun preorder (t)=
   
3.     let fun f (LEAF, vs) = vs
   
4.           | f (NODE(e,x,y), vs) = e::f (x, f (y, vs));
   
5.     in f (t, []) end;
   
6. 
   
7. fun inorder (t)=
   
8.     let fun f (LEAF, vs) = vs
   
9.           | f (NODE(e,x,y), vs) = f(x, e:: f(y, vs));
   
10.     in f(t, []) end;
    
11. 
    
12. fun postorder (t)=
    
13.     let fun f (LEAF, vs) = vs
    
14.           | f (NODE(e,x,y), vs) = f (x, f(y, e::vs));
    
15.     in f(t,[]) end;
    

复制代码

为提高效率，C 程序员通常要考虑一些硬件相关的，体系相关的问题，以榨取机器的全部潜能。Functional programming 的程序员通常在抽象层度更高一些的层次上来考虑问题，烦恼会少一些。但这并不等于函式编程不关心效率。函式编程的程序员可以通过算法提炼来提高效率。当然，让老板去买一台更强大的机器也是一个不错的选择。

win_hate

原帖由 MMMIX 于 2008-11-5 10:01 发表

这些 Haskell 也有支持，语法和 ML 也差不多，而且 Haskell 还能自动生成选择函数。

对，把这些语言和特性按时间串起来，就得到了一幅函式语言进化图。

drunkedcat

选择函数？

看起来怪怪地，还是直接叫 accessor 或者 getter 比较习惯些。呵呵。
每天都来个个版看看有没有新帖子，都成习惯了。

MMMIX

原帖由 drunkedcat 于 2008-11-5 14:03 发表
选择函数？

看起来怪怪地，还是直接叫 accessor 或者 getter 比较习惯些。呵呵。

知道什么意思就行了，不同的语言采用的术语不同也是常见的事情。

win_hate

原帖由 drunkedcat 于 2008-11-5 14:03 发表
选择函数？

看起来怪怪地，还是直接叫 accessor 或者 getter 比较习惯些。呵呵。
每天都来个个版看看有没有新帖子，都成习惯了。

看看固然不错。要是能每天在这个版发一两个帖子，那就更好了。

drunkedcat

原帖由 win_hate 于 2008-11-5 17:24 发表


看看固然不错。要是能每天在这个版发一两个帖子，那就更好了。

嗯，版主说得是。
我争取，只是这几天有些忙，等忙过这阵子的，继续看《The real world haskell》，到时一定多多发贴。