网络上有一项有趣的任务，在Twitter的一次采访中被问到。想象一下，您正在看轮廓中各种高度的墙。由于高度的差异，正在下雨，有水残留，有水流过墙的边缘。面临的挑战是确定墙壁之间还剩下多少水。
为了表示墙的顺序，我们可以使用以下列表：type Height = Int
walls :: [Height]
walls = [2,5,1,2,3,4,7,7,6]
为了找出每堵墙顶部的水量，我们需要知道三件事：- 当前墙高
- 最高左墙的高度
- 最高右墙的高度
我们找出下面的哪堵墙是右墙还是左墙，从最高的墙减去当前墙的高度并得到水量。让我们仔细看一个例子：
假设我们需要计算b墙的水量。最高的左墙高度a为3。最高的右墙s的高度为2。由于左墙较高，水将向右溢出，因此我们从右墙的高度开始计算。因此，水对所述壁的体积b是= 高度 Ç - 高度 B = 2 - 1 = 1。要解决此问题，列表的一遍是行不通的，但结果却是两遍-整个过程是计算左上和右上壁。（UPD：roman_kashitsyn展示了仅在没有获得每堵墙上积水量信息的情况下，一个墙是如何可能的）我们首先使用状态效应为每堵墙计算出最高的左墙：type Volume = Int
themax :: Height -> State Height Height
themax h = modify (max h) *> get
highest_left :: [Height] -> [Height]
highest_left walls = evalState (traverse themax walls) 0
现在，我们需要为每个墙计算最高的右墙，但是在这种情况下，我们需要从左侧而不是右侧开始计数。在这种情况下怎么办？上交名单？正如您可能从本文标题中猜到的那样，有一个更有趣的方法。逆应用函子
一个有趣的类型存在于“ 变形金刚”包中（从字面上的字面意义和象征意义上讲）。它允许您以相反的顺序运行应用效果：newtype Backwards f a = Backwards { forwards :: f a }
怎么运行的？让我们在仔细看看应用型的类实例的向后：
instance Applicative t => Applicative (Backwards t) where
pure = Backwards . pure
Backwards f <*> Backwards x = Backwards ((&) <$> x <*> f)
＆与$参数的函数应用相同，但参数顺序不同：首先是参数，然后是函数：f $ x = x & f
由于懒惰，我们首先计算应用性计算链的第二个部分，然后才计算第一个部分-因此是该类型的名称。在相同的变压器中，还有另一种有趣的类型- 反向：newtype Reverse f a = Reverse { getReverse :: f a }
它使用Backwards在反向Traversable中启动效果。
现在回到这种类型的原始问题。我们掌握月球漫步
“月步走”（源自英国的月球走步）或“向后滑动”是一种舞蹈技巧，当舞者向后移动时，同时模仿自己的双腿运动，就像向前走一样。（维基百科）。
为了提高技巧，我们将状态效果（就像我们从左到右向前移动）使用相同的函数，该函数用来计算最高的左墙：
themax :: Height -> State Height Height
themax h = modify (max h) *> get
highest_right :: [Height] -> [Height]
highest_right walls = getReverse $ evalState (traverse themax $ Reverse walls)
现在我们有了一切来计算累积水的总量。从最高的左侧和右侧的墙中选择最低的墙，然后从中减去墙的高度-这将是积水量：walls = [2,5,1,2,3,4,7,7,6]
let hls = highest_left walls = [2,5,5,5,5,5,7,7,7]
let hrs = highest_right walls = [7,7,7,7,7,7,7,7,6]
sum $ zipWith3 (\l x r -> min l r - x) hls walls hrs
因此，应用函子帮助我们从特定效果和数据结构中抽象出来。它们还有一些更有趣的用途- 分组查询，排序。此解决方案的源代码可在此处找到。这个难题有一些更有趣的方法，可以在这里查看。