在使用更高阶遍历函数找到有序遍历的第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

使用上面的有序函数，我想在不遍历整个列表的情况下获得第k个元素。

遍历有点像折叠，只要你给它传递一个函数和一个起始值。我想我可以通过传递k作为起始值来解决这个问题，并传递一个函数来递减k，直到它达到0，然后返回当前节点内的值。

我遇到的问题是，除了修改整个函数之外，我不太确定如何从有序遍历的递归中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

这将正确地短路。您可以使用标准差异列表技术使flatten的效率略高：

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

为了好玩，我还想展示如何在不使用累加器列表的情况下实现这个函数。相反，我们将生成一个有状态计算，它遍历树的"有趣"部分，当它到达第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

折叠列表的概念（至少？）有两个重要的推广。第一个更强大的概念是自同态。丹尼尔·瓦格纳答案的anyOldOrder遵循这种模式。

但对于你的特定问题，自同态概念比你需要的更强大。第二个较弱的概念是Foldable容器。CCD_ 18表达了容器的思想，其元素可以使用任意CCD_。这里有一个可爱的技巧：

{-# 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函数。CCD_ 25将CCD_ 26转换为列表，并将列表CCD_。事实证明，这种轻微的概括就是使列表转换高效所需的全部内容。

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

也就是说，当我们走到左边时，我们告诉它，当它完成时，它应该处理当前节点及其右子节点。

现在CCD_ 32并不是CCD_ 33最基本的运算；那实际上是

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