1

我正在做一份过去的函数编程试卷并有这个问题：

以下是编写基本相同表达式的两种方式：

f (g(x,y),z,h(t))

f (gxy) z (ht)

(a) 把这两个表达式画成两种不同的树，说明它们的不同结构。

(b) 定义 Haskell 数据类型 Bush a 和 Tree a 来捕获两种不同的结构。

我有点卡住了，因为我在我的课程中从来没有做过这样的事情。从后面的部分很明显，第一个表达式应该用 表示，Tree a第二个用表示Bush a，但我真的不知道从哪里开始。我猜想是这样的：

data Tree a = Leaf a | Node (Tree a) (Tree a)
data Bush a = Node a [Bush a]

但我认为二叉树类型不适合使用。有人能指出我正确的方向吗？

4

1 回答 1

4

实际上，第一个表达式由 表示，Bush第二个表达式由 表示Tree。

在 Haskell 中，g x y表示g x应用于y; 在 C 中，g(x, y)表示g应用于参数集合 - {x, y}。因此，在 C 中：

f(g(x,y),z,h(t)) = Bush f [Bush g [Bush x [], Bush y []], Bush z [], Bush h [Bush t []]]

  f
  +--g
  |  +--x
  |  +--y
  |
  +--z
  |
  +--h
     +--t

在 Haskell 中：

f (g x y) z (h t) = App (App (App f (App (App g x) y)) z) (App h t)

         +
        / \
       /  /\
      +  h  t  
     / \
    /\  z
   f  +
     / \
    /\  y
   g  x
于 2012-11-17T15:45:13.007 回答