是否存在适用于所有两指针问题的两遍扫描算法的 Haskell 推广？

Question

为了使这个问题变得非常精确和客观，我正在寻找除了“用某种多态数字类型替换

Int

”之外的任何重要概括。

在这个老问题中，提出了以下问题：

您将获得一个输入数组，其中每个元素代表线塔的高度。每个塔的宽度都是 1。开始下雨了。塔之间收集了多少水？

这是众所周知的基础编程练习。您可以在 Google 上以“Trapping Rain Water”的名称找到它。 答案中给出了一个非常好的解决方案：

rainfall :: [Int] -> Int
rainfall xs = sum (zipWith (-) mins xs)
    where mins = zipWith min maxl maxr
          maxl = scanl1 max xs
          maxr = scanr1 max xs

我想知道这是否可以推广，最好是推广到（所有）其他两指针问题。我发现

这个类似的SO问题

，但我没有找到完全令人满意的答案，因为它们专门针对问题中提到的特定问题。 特别是，我正在寻找与

Haskell 中的通用二分搜索实现

或 Haskell 中的通用图搜索算法具有相同风格的东西。

Answer 1

解决雨水滞留问题的优雅解决方案

使用了Tardis Monad，它可以让您在计算中向前和向后发送状态。

import Control.Monad.Tardis

levels hs = evalTardis (traverse 
  (\h -> do x <- min <$> getFuture <*> getPast -- Get the height of the enclosing walls
            modifyBackwards (`max` h)          -- Send the right max back to the past
            modifyForwards (`max` h)           -- Send the left max into the future
            pure (max 0 (x - h))               -- Calculate the height of the water itself
  ) hs) (0, 0)

美元水平总和 [5,3,7,2,6,4,5,9,1,2] 14

据我所知，

Tardis

允许您将任何两指针算法编写为单次遍历数据。通常从第二个指针获取的数据被“及时返回”发送到较早的步骤。唯一的问题是，如果你强制这两种状态，你就会陷入无限循环。

另请参阅 [此 Reddit 帖子]，了解

Tardis

的实际使用。

将

TardisT

与其他 monad 转换器结合起来将是一个有趣的练习。