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

问题描述

第3章定义了以下递归类型来表示二叉树:

Chapter 3 defines the following recursive type to represent a binary tree:

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

该练习要求我使用单个值构造函数来实现相同的类型，并使用"Maybe"类型来引用子节点:

The exercise requires I implement the same type using a single value constructor, using the "Maybe" type to refer to child nodes:

(摘自第60页的第3章练习2)

(From Chapter 3 Exercise 2 on page 60)

定义一个只有一个构造函数的树类型，例如我们的Java示例.请使用Maybe类型而不是Empty构造函数来引用节点的子代."

"Define a tree type that has only one constructor, like our Java example. Instead of the Empty constructor, use the Maybe type to refer to a node's children."

我想出的解决方案如下:

The solution I came up with is the following:

data AltTree a = AltNode a (Maybe (AltTree a)) (Maybe (AltTree a))
                 deriving (Show)

但是，这不允许包含其他空树的树，例如:

However, this does not allow for a tree containing other empty trees, such as:

AltNode 1 (AltNode 2 Nothing Nothing) (AltNode 3 Nothing Nothing)

我不确定为什么，"Nothing"不是"Maybe"类型的值构造函数吗?

And I'm not sure why, is "Nothing" not a value constructor for the "Maybe" type?

推荐答案

不是Nothing值构造函数会导致您的错误.传递给顶级树的两个分支的类型应为Maybe (AltTree a)，但是(AltNode 2 Nothing Nothing)和(AltNode 3 Nothing Nothing)的类型均应为AltTree Int.您必须使用Just值构造函数从中创建Maybe类型的值.喜欢

It's not the Nothing value constructor which causes your error. You two branches you pass to the top-level tree should have type Maybe (AltTree a), but both (AltNode 2 Nothing Nothing) and (AltNode 3 Nothing Nothing) have type AltTree Int. You have to use Just value constructor to create values of Maybe type from them. Like

AltNode 1 (Just (AltNode 2 Nothing Nothing)) (Just (AltNode 3 Nothing Nothing))

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