我有这个代数数据类型来表示二叉树:
data Tree a = Empty | Node a (Tree a) (Tree a)
deriving (Show, Eq)
我还有这个简单的类型:
data Step = StepL | StepR
deriving (Show, Eq)
另外,我需要定义一个函数:
1.采用[Step]
类型的路径,
1.要设置的值。我们的想法是从根节点开始,按照[Step]
中的“方向”到达目标节点。
如果路径没有“脱离”路径,我们将目标值重置为所需的值。(注意:我们重建整个树。)但是,如果路径丢失,我们将完整地返回输入树。
我最好的尝试:
-- path -> value -> current node -> original root -> new node
setHelper :: [Step] -> a -> Tree a -> Tree a -> Tree a
setHelper [] value (Node _ l r) root = Node value l r
setHelper [StepL] value (Node _ Empty Empty) root = root
setHelper [StepR] value (Node _ Empty Empty) root = root
setHelper [StepL] value (Node nodeValue l Empty) root = setHelper [] value l root
setHelper [StepR] value (Node nodeValue Empty r) root = setHelper [] value r root
setHelper [StepL] value (Node nodeValue Empty _) root = root
setHelper [StepR] value (Node nodeValue _ Empty) root = root
setHelper [StepL] value (Node _ l r) root = setHelper [] value l root
setHelper [StepR] value (Node _ l r) root = setHelper [] value r root
setHelper (StepL:steps) value (Node _ l r) root = setHelper steps value l root
setHelper (StepR:steps) value (Node _ l r) root = setHelper steps value r root
set :: [Step] -> a -> Tree a -> Tree a
set steps value root = setHelper steps value root root
现在,当我:
print (set [] 1 (Node 0 Empty Empty))
print (set [StepL, StepL] 1 (Node 0 (Node 0 (Node 0 Empty Empty) (Node 0 Empty Empty)) (Node 0 Empty Empty)))
print (set [StepL, StepR] 1 (Node 0 Empty Empty))
我得到:
Node 1 Empty Empty
Node 1 Empty Emtpy
*** Exception: Main.hs: ... Non-exhaustive patterns in function setHelper
正如您所看到的,我的实现既不正确又有bug。
Q:如何解决这两个问题?
2条答案
按热度按时间kyxcudwk1#
问题是没有一个子句匹配
setHelper [StepR] 0 Empty root
。如果你启用了编译器警告(例如ghc -Wall ...
),它也会告诉你:您可能只想转换这些内容:
转换成与最后2个子句相同的形式,即
[StepX]
→(StepX:steps)
等。还有一些多余的子句例如
两者都与
setHelper [StepL] 1 (Node 1 Empty Empty) Empty
匹配并执行完全相同的操作。现在是buggyness部分:你已经建立了相当多的(大多是冗余的)子句,所以让我们退后一步来思考这个问题。当我们调用
set
时,我们知道我们已经完成的情况是什么(又名基本情况),没有什么可以做的,我提出了以下两个:1.我们已经走下了小路,降落在一个
Empty
上在这种情况下,我们只返回相同的东西,因为我们不想改变树中的任何东西。我们不需要返回
root
,因为在我们之前的任何东西都可以(并且应该)由set
的先前调用(即递归调用)1.我们已经到达了旅程的终点
在这里,我们只是返回一个新的节点,旧的子树作为我们的孩子,不需要重建这些,因为它们会保持不变。同样,我们不关心在我们之前发生的任何事情,递归案例将处理这些。
现在基本情况已经正确处理了,我们可以看看递归步骤:
1.我们不需要检查
l == Empty
,我们的基本case将处理它,但我们必须做的是将递归调用的新生成的case放在旧的l
的位置。1.我们向右走,但这与
r
相同,而不是l
,因此实现留给读者。有了这4个子句,
set
函数是total,并生成新树。特别注意:
[StepL]
上进行匹配(一个步骤),因为我们的递归情况(StepL:steps)
与[]
基本情况的组合将为我们处理这个问题。root
串,因为我们总是沿着路径构建一棵新树。root
,因此也不需要set
<->setHelper
对来简化set
的调用[StepX]
匹配。通常,一个递归的(x:xs)
和一个[]
组合起来就可以很好地完成这项工作。uxhixvfz2#
基本上有两个问题:你定义了两种情况。最多可能有六种情况:对于第一个列表可以是空的
[]
,以StepL
或StepR
开始,所以有三种情况。对于第二个值,它可以是Empty
或Node … …
,因此第一种模式有三种情况,第二种模式有两种情况,这意味着总共有六种情况,* 大约 *。是的,在某些情况下,你必须深入研究一个值,而不仅仅是外部数据构造函数,但实际上这种情况并不多,所以通常你可以从“浅”模式开始。第二个问题是,在Haskell中,一切都是“不可变的”。因此,您不需要更改节点的值,而是构建一个新的
Tree
,在其中可以重用旧树的部分内容,并为我们想要重置的位置添加一个不同的节点。因此,传递root
并返回root
也很奇怪。考虑到这一点,我们可以设计一个看起来像这样的函数:
这就足够了:通过填充
...
部分。