haskell - Haskell : which wins? 中不同二叉树的定义

Question

我习惯了以下 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 只是 Node a Empty Empty ，这个构造函数应该存在吗？我们也可以删除 Empty ，使用一个独特的构造函数，如

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

或类似的东西。

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

Answer 1

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

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

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