Section: 2.3 Recursive Types

第 2.3 节 递归类型

data Tree a = Leaf a | Branch (Tree a) (Tree a)    deriving Show

The following typings are implied by this declaration. As before, this is not valid Haskell syntax.

这个声明隐含了下面的类型。和之前一样，这不是合法的 Haskell 语法。

Leaf :: a -> Tree a
Branch :: Tree a -> Tree a -> Tree a

fringe :: Tree a -> [a]
fringe (Leaf x) = [x]
fringe (Branch left right) = fringe left ++ fringe right

The following trees can be used to test functions:

下面的树可以用来测试函数：

tree1 :: Tree Int
tree1 = Branch (Leaf 1) (Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 4))
tree2 :: Tree Int
tree2 = Branch (Branch (Leaf 3) (Leaf 1)) (Branch (Leaf 4) (Leaf 1))
tree3 :: Tree Int
tree3 = Branch tree1 tree2

Try evaluating fringe tree1 and others.

试试求值 fringe tree1 以及其他表达式。

Here's another tree function:

这是另一个树的函数：

twist :: Tree a -> Tree a
twist (Branch left right) = Branch right left
twist x = x        -- This equation only applies to leaves

Here's a function which compares two trees to see if they have the same shape. Note the signature: the two trees need not contain the same type of values.

这里有一个比较两棵树形状是否相同的函数。注意它的签名：这两棵树不必

包含同一种类型的值。

sameShape :: Tree a -> Tree b -> Bool
sameShape (Leaf x) (Leaf y) = True
sameShape (Branch l1 r1) (Branch l2 r2) = sameShape l1 l2 && sameShape r1 r2
sameShape x y = False  -- One is a branch, the other is a leaf

The && function is a boolean AND function.

&& 是一个布尔与函数。

The entire pattern on the left hand side must match in order for the right hand side to be evaluated. The first clause requires both arguments to be a leaf' otherwise the next equation is tested. The last clause will always match: the final x and y match both leaves and branches.

只有左边的整个模式都匹配成功，右边的表达式才会被求值。第一个子句要求

两个参数都是叶（leaf），否则就测试下一条方程。最后一个子句永远会匹配：

最后的 x 和 y 既能匹配叶也能匹配分支。

This compares a tree of integers to a tree of booleans.

这行把一个整数树和一个布尔值树进行比较。

e1 = sameShape tree1 (Branch (Leaf True) (Leaf False))