haskell 设置二叉树中节点的值

ggazkfy8  于 2023-06-06  发布在  其他
关注(0)|答案(2)|浏览(217)

我有这个代数数据类型来表示二叉树:

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:如何解决这两个问题?

kyxcudwk

kyxcudwk1#

问题是没有一个子句匹配setHelper [StepR] 0 Empty root。如果你启用了编译器警告(例如ghc -Wall ...),它也会告诉你:

tree.hs:20:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘setHelper’:
        Patterns not matched:
            [] _ Empty Empty
            [] _ Empty (Node _ _ _)
            (StepL:_:_) _ Empty Empty
            (StepL:_:_) _ Empty (Node _ _ _)
            ...

您可能只想转换这些内容:

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

转换成与最后2个子句相同的形式,即[StepX](StepX:steps)等。
还有一些多余的子句例如

setHelper [StepL] value (Node _ Empty Empty) root = root
setHelper [StepL] value (Node nodeValue Empty _) root = root

两者都与setHelper [StepL] 1 (Node 1 Empty Empty) Empty匹配并执行完全相同的操作。
现在是buggyness部分:你已经建立了相当多的(大多是冗余的)子句,所以让我们退后一步来思考这个问题。当我们调用set时,我们知道我们已经完成的情况是什么(又名基本情况),没有什么可以做的,我提出了以下两个:
1.我们已经走下了小路,降落在一个Empty

set steps value Empty = Empty

在这种情况下,我们只返回相同的东西,因为我们不想改变树中的任何东西。我们不需要返回root,因为在我们之前的任何东西都可以(并且应该)由set的先前调用(即递归调用)
1.我们已经到达了旅程的终点

set [] value (Node _ l r) = Node value l r

在这里,我们只是返回一个新的节点,旧的子树作为我们的孩子,不需要重建这些,因为它们会保持不变。同样,我们不关心在我们之前发生的任何事情,递归案例将处理这些。
现在基本情况已经正确处理了,我们可以看看递归步骤:
1.我们不需要检查l == Empty,我们的基本case将处理它,但我们必须做的是将递归调用的新生成的case放在旧的l的位置。
1.我们向右走,但这与r相同,而不是l,因此实现留给读者。
有了这4个子句,set函数是total,并生成新树。
特别注意:

  • 我们不必在[StepL]上进行匹配(一个步骤),因为我们的递归情况(StepL:steps)[]基本情况的组合将为我们处理这个问题。
  • 我们不需要沿着root串,因为我们总是沿着路径构建一棵新树。
  • 由于我们不需要在每次调用中都使用root,因此也不需要set <->setHelper对来简化set的调用
  • 基本情况很少需要在非空列表上匹配,比如[StepX]匹配。通常,一个递归的(x:xs)和一个[]组合起来就可以很好地完成这项工作。
  • 有时候从一开始就不清楚基本情况是什么,假装你已经实现了它们并从递归情况开始是很好的,只要确保最终实现它们并把它们放在第一位,因为子句是从上到下检查的。
uxhixvfz

uxhixvfz2#

基本上有两个问题:你定义了两种情况。最多可能有六种情况:对于第一个列表可以是空的[],以StepLStepR开始,所以有三种情况。对于第二个值,它可以是EmptyNode … …,因此第一种模式有三种情况,第二种模式有两种情况,这意味着总共有六种情况,* 大约 *。是的,在某些情况下,你必须深入研究一个值,而不仅仅是外部数据构造函数,但实际上这种情况并不多,所以通常你可以从“浅”模式开始。
第二个问题是,在Haskell中,一切都是“不可变的”。因此,您不需要更改节点的值,而是构建一个新的Tree,在其中可以重用旧树的部分内容,并为我们想要重置的位置添加一个不同的节点。因此,传递root并返回root也很奇怪。
考虑到这一点,我们可以设计一个看起来像这样的函数:

setHelper :: [Step] -> a -> Tree a -> Tree a
-- end of path, empty, we fall off the path
setHelper [] _ Empty = ...
-- end of path, node, replace value
setHelper [] v' (Node _ l r) = ...
-- turn left: construct new Node with left subtree modified
setHelper (StepL:steps) v' (Node v l r) = ...
-- turn right: construct new Node with right subtree modified
setHelper (StepR:steps) v' (Node v l r) = ...
-- we fall of the tree, just return the current node
setHelper (_:_) _ Empty = ...

这就足够了:通过填充...部分。

相关问题