使用高阶遍历函数找到中序遍历的第k个元素后中断

Question

我有以下代码来对二叉树进行中序遍历：

data BinaryTree a =
  Node a (BinaryTree a) (BinaryTree a)
  | Leaf
  deriving (Show)

inorder :: (a -> b -> b) -> b -> BinaryTree a -> b
inorder f acc tree = go tree acc
  where go Leaf z = z
        go (Node v l r) z = (go r . f v . go l) z

使用上面的 inorder 函数我想得到第 k 个元素，而不必遍历整个列表。

考虑到您向它传递了一个函数和一个起始值，遍历有点像折叠。我在想我可以通过传递 k 作为起始值来解决它，并且一个函数会递减 k 直到它达到 0 并且在那个时候 returns 当前内部的值节点。

我的问题是我不太确定如何break 摆脱中序遍历的递归而不是修改整个函数，但我觉得必须修改高阶函数废墟首先使用高阶函数的要点。

有没有办法在 k 次迭代后中断？

Answer 1

我观察到go在左右子树上递归调用的结果对f不可用；因此无论 f 做什么，它都不能选择忽略递归调用的结果。因此我相信 inorder 所写的总是遍历整棵树。 (edit: 复习一下，这个说法可能有点强，好像f可能有机会忽略左子树，但基本成立，没有理由以这种方式将左子树提升到右子树之上。）

更好的选择是递归调用 f。例如：

anyOldOrder :: (a -> b -> b -> b) -> b -> BinaryTree a -> b
anyOldOrder f z = go where
    go Leaf = z
    go (Node v l r) = f v (go l) (go r)

现在写

flatten = anyOldOrder (\v ls rs -> ls ++ [v] ++ rs) []

我们会发现flatten已经够懒了：

> take 3 (flatten (Node 'c' (Node 'b' (Node 'a' Leaf Leaf) Leaf) undefined))
"abc"

（undefined 用于证明在遍历过程中从未检查过这部分树。）因此我们可以写成

findK k = take 1 . reverse . take k . flatten

这将正确短路。您可以使用标准 difference list 技术使 flatten 稍微更有效率：

flatten' t = anyOldOrder (\v l r -> l . (v:) . r) id t []

只是为了好玩，我还想展示如何在不使用累加器列表的情况下实现此功能。相反，我们将生成一个有状态的计算，它遍历树的 "interesting" 部分，在到达第 k 个元素时停止。有状态计算如下所示：

import Control.Applicative
import Control.Monad.State
import Control.Monad.Trans.Maybe

kthElem k v l r = l <|> do
    i <- get
    if i == k
        then return v
        else put (i+1) >> r

看起来很简单，嘿？现在我们的 findK 函数将转移到 kthElem，然后做一些新类型的解包：

findK' k = (`evalState` 1) . runMaybeT . anyOldOrder (kthElem 3) empty

我们可以验证它是否仍然像我们期望的那样懒惰：

> findK' 3 $ Node 'c' (Node 'b' (Node 'a' Leaf Leaf) Leaf) undefined
Just 'c'

Answer 2

折叠列表的概念有（至少？）两个重要的概括。第一个更强大的概念是变形。 Daniel Wagner 的回答 anyOldOrder 遵循这种模式。

但是对于您的特定问题，变质概念比您需要的更强大。第二个较弱的概念是 Foldable 容器。 Foldable 表达了一个容器的想法，其元素可以使用任意 Monoid 的操作混合在一起。这是一个可爱的把戏：

{-# LANGUAGE DeriveFoldable #-}

-- Note that for this trick  only I've 
-- switched the order of the Node fields.
data BinaryTree a =
  Node (BinaryTree a) a (BinaryTree a)
  | Leaf
  deriving (Show, Foldable)

index :: [a] -> Int -> Maybe a
[] `index` _ = Nothing
(x : _) `index` 0 = Just x
(_ : xs) `index` i = xs `index` (i - 1)

(!?) :: Foldable f => Int -> f a -> Maybe a
xs !? i = toList xs `index` i

然后你可以只使用 !? 索引到你的树中！

这个技巧很可爱，实际上推导 Foldable 非常方便，但它不会帮助您理解任何东西。我将首先展示如何在不使用 Foldable.

的情况下相当直接有效地定义 treeToList

treeToList :: BinaryTree a -> [a]
treeToList t = treeToListThen t []

神奇之处在于 treeToListThen 函数。 treeToListThen t more 将 t 转换为列表并将列表 more 附加到结果的末尾。这种轻微的概括证明是有效转换为列表所需的全部。

treeToListThen :: BinaryTree a -> [a] -> [a]
treeToListThen Leaf more = more
treeToListThen (Node v l r) more =
  treeToListThen l $ v : treeToListThen r more

我们不是先对左子树进行中序遍历然后追加其他所有内容，而是告诉左遍历完成后将什么粘贴到最后！这避免了重复列表连接的潜在严重低效率，在糟糕的情况下可以将事情变成 O(n^2)。

回到Foldable的概念，把东西变成列表是foldr的一个特例：

toList = foldr (:) []

那么我们如何为树实现 foldr 呢？它最终有点类似于我们对 toList:

所做的

foldrTree :: (a -> b -> b) -> b -> BinaryTree a -> b
foldrTree _ n Leaf = n
foldrTree c n (Node v l r) = foldrTree c rest l
  where
    rest = v `c` foldrTree c n r

也就是说，当我们从左边往下走的时候，我们告诉它，当它完成后，它应该处理当前节点及其右侧child。

现在 foldr 并不是 Foldable 的最基本操作；那实际上是

foldMap :: (Foldable f, Monoid m)
        => (a -> m) -> f a -> m

可以使用 foldMap 实现 foldr，使用特殊的 Monoid 以一种有点棘手的方式。我现在不想给你过多的细节，除非你问（但你应该看看 Data.Foldable 中 foldr 的默认定义）。相反，我将展示如何使用 Daniel Wagner 的 anyOldOrder:

来定义 foldMap

instance Foldable BinaryTree where
  foldMap f = anyOldOrder bin mempty where
    bin lres v rres = lres <> f v <> rres

使用高阶遍历函数找到中序遍历的第k个元素后中断

Breaking after finding the kth element of an inorder traversal using a higher order traversal function

algorithm

binary-tree

haskell