真实世界 Haskell 第 3 章练习：具有 1 个值构造函数的二叉树 - 跟进

Question

此题不重复

在我看来，

A question with the same title already exists, but the answer 只解决了部分问题，我也对它没有回答的问题感兴趣。

前言

真实世界 Haskell 在第 3 章第 58 页中提出了二叉树数据类型的以下定义，

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

它提供了两个构造函数（用于空和 non-empty Trees）。

另一方面，在第 60 页，练习挑战 reader 使用单个构造函数定义 Tree 数据类型。

经过几次尝试，我想出了与上面链接相同的解决方案：

data Tree a = Node a (Maybe (Tree a)) (Maybe (Tree a)) deriving(Show)

链接问题中未回答的内容

这个定义的缺点是它不允许实例化空的Tree，尽管它允许通过以下语法实例化空的children的Tree :

Node 3 Nothing (Just (Node 2 Nothing Nothing))

我认为没有比上面更好的解决方案了，如果没有 "standalone" 空树是可以接受的并且要求只使用一个构造函数。

对上述声明有一些评论就好了；但是，我的主要问题是如何使用一个构造函数定义 Tree，以便实例化一个空的 Tree?

既然我已经写了这个问题，我认为一个可能的答案如下，我一点也不确定：

如果一个 children 是否为空被编码为它是通过 Nothing 还是 Just (Node ...) 构造的，对于整棵树来说几乎是一样的（或根节点），它确实可以将自己定义为 Nothing 或 Just (Node ...)；这就是说只有一个构造函数，Nothing 是实例化一棵空树的方法。（换句话说，我只是开始认为这个问题本来就是"ill-formed"。不过我会post它，因为我认为我可以学到一些东西你comments/answers。）

以上是否有意义？

一个可能的答案

原问题中的评论提出了以下解决方案

data Tree a = Tree (Maybe (a,Tree a,Tree a))

这（我的理解）允许通过 Node Nothing 实例化一棵空树，或通过 Node (Just (value,child1,child2)).

实例化一棵 non-empty 树

Answer 1

提示：您可以使用 n 元组类型将任何 n 元构造函数转换为 1 元构造函数。

例如，您的树类型与以下树类型同构：

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

我认为您现在应该能够将此类型转换为仅涉及一个构造函数的类型。

Answer 2

@chi 的回答以及他的评论说明了一切，可以通过以下任一方式完成：

data Tree a = T (Either () (a, Tree a, Tree a)) deriving Show

树的一个例子是：

node1 = T $ Right ("data node 1", node2, node3)
node2 = T $ Left ()
node3 = T $ Right ("data node 3", node2, node2)

  $> node1
T (Right ("data node 1",T (Left ()),T (Right ("data node 3",T (Left ()),T (Left ())))))

不过大家也都说了，可以用Maybe代替，因为Either ()可以看成Maybe a

真实世界 Haskell 第 3 章练习：具有 1 个值构造函数的二叉树 - 跟进

Real World Haskell Chapter 3 excercise: Binary Tree with 1 value constructor - follow up

tree

haskell

maybe