真实世界Haskell第3章练习:具有1个值构造函数的二叉树-后续 [英] Real World Haskell Chapter 3 excercise: Binary Tree with 1 value constructor - follow up

问题描述

此问题不是重复的

同一个问题标题已经存在，但是在我看来，答案仅部分解决了该问题，我也对它没有被保留的东西.

A question with the same title already exists, but the answer only partially addressed it, in my opinion, and I am interested also in what it left unaswered.

前言

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

Real World Haskell proposes, in Chapter 3, page 58, the following definition for a binary tree datatype,

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

提供了两个构造函数(用于空和非空Tree s).

which provides two constructors (for empty and non-empty Trees).

另一方面，在第60页上，练习使读者挑战如何使用单个构造函数来定义Tree数据类型.

On the other hand, at page 60, an exercise challenges the reader to define the Tree datatype by using a single constructor.

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

After several attempts, I came up with the same solution as the one linked above:

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

链接的问题中未解答的内容

此定义的缺点是，它不允许实例化为空的Tree，尽管它允许通过以下语法实例化具有空子元素的Tree:

The drawback of this definition is that it does not allow the instantiation of an empty Tree, although it allows the instantiation of a Tree with empty children through the following syntax:

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

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

I think that there's not much a better solution than the above, if not having a "standalone" empty tree is acceptable and the requirement is to use one constructor only.

对以上陈述发表评论将是一件很不错的事；但是，我的主要问题是如何使用一个构造函数定义Tree，以便可以实例化空的Tree?

Having some comment on the above statement would be nice; however, my main question is how can I define Tree with one constructor such that I can instantiate an empty Tree?

现在我已经写了这个问题，我认为以下是一个可能的答案，我完全不确定:

Now that I've written the question, I think that one possible answer is the following, of which I am not at all sure:

如果是否通过Nothing或Just (Node ...)构造子对象而将其编码为空，则整个树(或根节点)的情况几乎相同，实际上可以自行定义作为Nothing或Just (Node ...)；这就是说，只有一个构造函数，Nothing是实例化一棵空树的方法. (换句话说，我只是开始认为该问题本质上是形式不正确的".尽管如此，我还是将其发布，因为我认为我可以从您的评论/答案中学到一些东西.)

If a children being empty or not is encoded in whether it is costructed through Nothing or Just (Node ...), pretty much the same holds for the whole tree (or root node), which can be indeed defined itself as a Nothing or Just (Node ...); this is to say that with only one constructor, Nothing is the way to instanciate an empty tree. (In other words, I'm just starting to think that this question is inherently "ill-formed". Notheless I'll post it, as I think I can learn something your comments/answers.)

以上内容有意义吗?

可能的答案

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

A comment in the original question proposes the following solution

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

(据我所知)可以通过Node Nothing实例化一个空树，或者通过Node (Just (value,child1,child2))实例化一个非空树.

which (my understanding) allows to instantiate an emtpy tree by Node Nothing, or a non-empty tree by Node (Just (value,child1,child2)).

推荐答案

这里有个提示:您可以使用n元组类型将任何n元的构造函数转换为1元的构造.

Here's a hint: you can turn any n-ary constructor into a 1-ary one using a n-tuple type.

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

For instance, your tree type is isomorphic to the following one:

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

我认为您现在应该可以将这种类型转换为仅涉及一个构造函数的类型.

I think you should now be able to turn this type into one which only involves one constructor.

这篇关于真实世界Haskell第3章练习:具有1个值构造函数的二叉树-后续的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！