在 Haskell 的树上尝试 takeWhile 的一个版本

Question

给定一棵看起来像这样的树：

data Tree a = Leaf | Node (Tree a) a (Tree a)

折叠函数如下所示：

foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree _ b Leaf         = b
foldTree fn b (Node lt x rt) = f (foldTree fn b lt) x (foldTree fn b rt)

我希望能够编写如下所示的 takeWhileTree 函数：

treeTakeWhile :: (a -> Bool) -> Tree a -> Tree a

我希望它模仿 'normal' 列表 takeWhile 函数，以便它 return 是其元素满足给定条件的最大可能树。

所以，如果一棵树 t = Node (Node Leaf 10 Leaf) 4 (Node Leaf 5 Leaf)，那么：

treeTakeWhile (> 5) T = Leaf
treeTakeWhile (>= 4) T = T
treeTakeWhile (< 5) T = Node Leaf 4 Leaf
treeTakeWHile (< 8) T = Node Leaf 4 (Node Leaf 5 Leaf)

到目前为止，我似乎无法确定要传递给 foldTree 的内容。在foldtree的定义中，函数可以分解为：b可能是左子树，a可能是当前节点中的值，b可能是右子树。

因此，传递给 treeTakeWhile 的函数必须以某种方式应用于节点的所有这些部分，同时能够在操作不再适用时停止。

treeTakeWhile fn = foldTree (\xs x ys -> if y then g else Leaf) Node()
              where g = (lt, x, rt)
                    y = fn (Node lt x rt)

上面显然是错误的，但是我不确定如何在这里表达将函数应用于当前节点的值后跟左树和右树的行为。有人能指出我正确的方向吗？折叠将如何产生所需的树？

编辑 1：

好的，根据你的反馈，我已经到了一个我认为我非常接近答案但无法弄清楚为什么编译器仍然抱怨的地方：

treeTakeWhile :: (a -> Bool) -> Tree a -> Tree a
treeTakeWhile c = foldTree f acc
        where acc = Leaf
              f l x r = if c x then Node (f lt) x (f rt) else Leaf

据我所知，foldTree 现在正在传递正确的参数。并且谓词也在树的每个级别上根据需要进行评估。 return 值也始终是 Tree 类型。

Answer 1

与其立即使用 foldTree，不如先定义函数本身。

这里基本上就三个选项：

树是Leaf，不管条件是什么，结果也是Leaf；
树是一个Node并且条件满足，然后我们产生元素，并在子树上递归；
树是Node，条件不满足，则结果是Leaf.

我们可以将这些规则编码为：

treeTakeWhile :: (a -> Bool) -> Tree a -> Tree a
treeTakeWhile c = go
    where go Leaf = Leaf                                -- (1)
          go (Node l x r) | c x = Node (go l) x (go r)  -- (2)
                          | otherwise = Leaf            -- (3)

这会产生预期的结果：

Prelude> treeTakeWhile (>5) t
Leaf
Prelude> treeTakeWhile (>=4) t
Node (Node Leaf 10 Leaf) 4 (Node Leaf 5 Leaf)
Prelude> treeTakeWhile (<5) t
Node Leaf 4 Leaf
Prelude> treeTakeWhile (<8) t
Node Leaf 4 (Node Leaf 5 Leaf)

将其移动到 `foldTree`

现在我们的目标是将逻辑移动到foldTree，因此我们可以将函数写成：

treeTakeWhile :: (a -> Bool) -> Tree a -> Tree a
treeTakeWhile c = foldTree f x0
    where f tl x tr = -- ...
          x0 = -- ...

x0 是我们应该为 Leaf 填写的值，但我们已经知道那是什么：它是第一个规则 (1)，因此我们应该 return 还有一个Leaf

对于f，我们需要一个函数Tree a -> a -> Tree a -> Tree a。第一个操作数 tl 是左子树的 treeTakeWhile （这相当于原始函数实现中的 go l ），第二个参数 x 是编码的值Node，最后一个参数tr是第二个子树上treeTakeWhile的结果（所以等价于go r），所以：

treeTakeWhile :: (a -> Bool) -> Tree a -> Tree a
treeTakeWhile c = foldTree f x0
    where f tl x tr = -- ...
          x0 = -- ...

（留作练习）。

在 Haskell 的树上尝试 takeWhile 的一个版本

Trying a version of takeWhile on trees in Haskell

binary-tree

haskell

functional-programming

将其移动到 `foldTree`

在 Haskell 的树上尝试 takeWhile 的一个版本

Trying a version of takeWhile on trees in Haskell

binary-tree

haskell

functional-programming

将其移动到 foldTree

将其移动到 `foldTree`