ML 趣题：树的类型

code17's picture
Thu, 2008/10/09 - 22:25 — code17

这道也是老题了。(下面我们用OCaml作代码示例，SML或Haskell完全类似。)

  • 请用 Leaf 和 Node 这两个 constructors (i.e., variants) 来定义一个二叉树类型，使得以下表达式 number 和· tree 可以通过类型检测
  • 写出在这种定义下 number 的具体类型，并解释为什么
let rec number = function
  | Leaf _ -> 1
  | Node (_, tl, tr) -> 1 + number tl + number tr;;

let tree =
  Node ( [1;2;3] ,
         Node ( "function" ,
                Leaf None,
                Node ( succ,
                       Node ( Some 'c',
                              Node ( 3.1415,
                                     Leaf [],
                                     Leaf abs ),
                              Leaf "leaf" ),
                       Leaf [99] ) ),
         Leaf (log 10.)
       );;

...... full content is only available to community members.

  • Login to post comments
  • 254 reads

Fri, 2008/10/10 - 11:13 — fishmacs

fishmacs's picture

这样也可以？

...... full content is only available to community members.

Fri, 2008/10/10 - 11:16 — fishmacs

fishmacs's picture

我以为只有动态语言能这么搞

...... full content is only available to community members.

Sun, 2008/10/12 - 00:09 — roy_hu

roy_hu's picture

答案什么时候公布？

...... full content is only available to community members.

------------分割线----------------------
http://sites.google.com/site/haskell/
http://sites.google.com/site/ocaml/

Sun, 2008/10/12 - 18:17 — code17

code17's picture

第一问的答案

...... full content is only available to community members.

Mon, 2008/10/13 - 00:01 — roy_hu

roy_hu's picture

哎，差了点

...... full content is only available to community members.

------------分割线----------------------
http://sites.google.com/site/haskell/
http://sites.google.com/site/ocaml/

Mon, 2008/10/13 - 04:44 — roy_hu

roy_hu's picture

还要颠倒类型变量的顺序。。

...... full content is only available to community members.

------------分割线----------------------
http://sites.google.com/site/haskell/
http://sites.google.com/site/ocaml/

Wed, 2008/12/03 - 13:38 — fishmacs

fishmacs's picture

不是很明白

...... full content is only available to community members.

Wed, 2008/12/03 - 15:51 — roy_hu

roy_hu's picture

因为5个类型变量被unify了

...... full content is only available to community members.

------------分割线----------------------
http://sites.google.com/site/haskell/
http://sites.google.com/site/ocaml/

Thu, 2008/12/04 - 00:37 — code17

code17's picture

polymorphic recursion

...... full content is only available to community members.