4

我习惯了以下Tree定义：

data Tree a = Empty | Node a (Tree a) (Tree a)

直到我在某个地方遇到这个：

data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)

这让我对 Haskell 习语感到好奇。

既然Leaf a是 just Node a Empty Empty，这个构造函数应该存在吗？我们也可以删除Empty，使用一个独特的构造函数，比如

Tree (Maybe (a, (Tree a), (Tree a)))

或类似的东西。

我写的第二个定义是“最扩展”的一个，第一个定义介于它和最后一个之间。什么是实际和理论上最好的？换句话说，性能和数据类型的设计呢？

4

2 回答 2

7

如果您想要惯用的 Haskell，请使用第一个定义，因为这样您就可以使用较少的构造函数进行模式匹配。

如果您有带有很多叶子的巨大二叉树，如果您想为Tree a每个叶子节省大约 16 个字节（额外指针）的内存（很大程度上取决于您使用的平台/编译器有多少内存） ，请使用第二个定义保存）。

您提出的第三种选择在技术上是有效的表示（假设您的意思是Tree (Maybe (a, Tree a, Tree a))，但使用起来非常乏味。

于 2012-07-31T20:29:18.433 回答
6

dflemstr 的答案是正确的，但我想我会添加两个评论（不能通过对原始答案的评论来容纳）。

首先，按照第二个定义可以节省内存的相同逻辑，可以为这个定义一个类似的论点：

data Tree a = Empty 
            | Leaf a 
            | LeftOnly a (Tree a) 
            | RightOnly a (Tree a) 
            | Branch a (Tree a) (Tree a)

这是否真的重要取决于您的应用程序。

第二个也是更重要的一点是，如果您避免直接使用数据构造函数，您可以从这些实现选择中抽象出来。例如，foldTree可以为这些类型中的任何一种编写等效函数。对于较短的类型，您可以这样做：

data Tree a = Empty | Node a (Tree a) (Tree a)

foldTree :: (a -> b -> b -> b) -> b -> Tree a -> b
foldTree f z Empty = z
foldTree f z (Node v l r) = f v (subfold l) (subfold r)
    where subfold = foldTree f z

对于更长的，你可以这样写：

data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)

foldTree :: (a -> b -> b -> b) -> b -> Tree a -> b
foldTree f z Empty = z
foldTree f z (Leaf v) = f v z z
foldTree f z (Node v l r) = f v (subfold l) (subfold r)
    where subfold = foldTree f z

对于您Maybe的基于 - 的替代方案或我的五构造函数替代方案也可以这样做。此外，这种技术可以应用于您需要的树上的任何其他通用函数。（事实上​​，很多这样的函数都可以用 来写foldTree，所以大部分都超出了上面的定义。）

于 2012-07-31T21:54:26.960 回答