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

Question

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

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

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

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

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

我想出的解决方案如下:

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

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

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

而且我不确定为什么,"Nothing"不是"Maybe"类型的值构造函数？

Answer 1

它不是Nothing导致错误的值构造函数.你们两个分支传递给顶层树应该有类型Maybe (AltTree a),但都(AltNode 2 Nothing Nothing)和(AltNode 3 Nothing Nothing)有型AltTree Int.您必须使用Just值构造函数Maybe从它们创建类型的值.喜欢

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