haskell - 描绘mapAccumR 的工作原理

Question

您能否解释一下 mapAccumR 的具体工作原理、它解决的问题类型以及它与 foldr 有何不同。我很难想象它是如何工作的。

Answer 1

这是一个好问题。我希望文档在这方面能更好一点。我最近自己也使用过它们，所以希望我能从那些在理解它们的工作原理上也遇到困难的人的角度来解释。

因此，mapAccumR的类型签名是:

可遍历 t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)

让我们假设所讨论的 Traversable 是一个列表，因为这种方式可能更容易理解，所以专门化类型:

(a -> b -> (a, c)) -> a -> [b] -> (a, [c])

因此，为了解释这一点，mapAccumR 是一个包含三个参数的函数(忽略柯里化(Currying)，因为我们为了便于解释而这样做)，我将在此处注释这些参数:

mapAccumR :: (a -> b -> (a, c))             -> a                     -> [b]           -> (a, [c])
mapAccumR :: mappingAndAccumulationFunction -> initialAccumulatorValue -> listToMapOver -> resultantAccumulatorAndMappedListPair

很酷，这样就可以一点弄清楚事情，但它仍然有点令人困惑，对吧。那么它到底有什么作用呢？

嗯，它做了一个累积映射:所以我们说第一步，它所做的就是从 listToMapOver 中获取 initialAccumulatorValue 和第一个 b ，并将它们传递给 mappingAndAccumulationFunction 函数，该函数将对它们执行某些操作并返回两件事: 1. 类型为 a< 的新值 和 2. 稍后收集到映射列表中的映射值(请参阅 resultantAccumulatorAndMappedListPair 的类型)。这两个值是成对的，因此 mappingAndAccumulationFunction 函数的返回类型为 (a, c)。

在第二步和后续步骤中，它从上一步中获取此 (a, c) 对，将 c 拉出并通过将其附加到它一直跟踪到最后的内部列表，并将 a 与下一个 b 一起作为 mappingAndAccumulationFunction 的下一个应用程序的第一个参数拉出。 code> listToMapOver 的值。

一旦用完 listToMapOver 中的 b 值，它就会返回一个包含 a 最后一个值的对以及一个其内容的列表属于 c 类型。

那么你到底为什么想要这个功能呢？示例时间!

annotateLeastFavourites items = snd (mapAccumR (\num item -> (num + 1, show num ++ ": " ++ item)) 1 items)

itemList = ["Geese","Monkeys","Chocolate","Chips"]

> annotateLeastFavourites itemList
["4: Geese","3: Monkeys","2: Chocolate","1: Chips"]

或者，也许这样更容易看出发生了什么:

> mapAccumR (\num item -> (num + 1, show num ++ ": " ++ item)) 1 ["Geese", "Monkeys", "Chocolate", "Chips"]
(5,["4: Geese","3: Monkeys","2: Chocolate","1: Chips"])

所以我们可以看到，它是一个函数，可以在我们需要一些信息来传递 map 时，例如，或者如果我们想要建立一个集合值(右侧)还需要传递随每个步骤而变化的信息(左侧的值)。

也许您想获取项目列表的最大长度，因为您还用每个项目的长度对它们进行注释

> mapAccumR (\biggestSoFar item -> (max biggestSoFar (length item), (item, length item))) 0 ["Geese", "Monkeys", "Chocolate", "Chips"]
(9,[("Geese",5),("Monkeys",7),("Chocolate",9),("Chips",5)])

这里有很多可能性。希望现在已经清楚为什么人们说这就像 map 和 foldr 的组合。如果您碰巧像我一样从几何角度思考，我认为当您需要转换某种集合时，您需要将一些变化的事物作为转换的一部分通过该集合进行线程化。

希望这可以帮助您获得直觉，并将该模式​​存储在您的脑海中，以便以后您认识到您将来可能需要它时:)

let (_, result) =
  mapAccumR 
    (\cumulativeLength item -> 
      let newLength = cumulativeLength + length item 
      in (newLength, take cumulativeLength (repeat ' ') ++ item)
    )
    0
    ["Geese", "Monkeys", "Chocolate", "Chips", "Dust", "Box"]
in mapM_ putStrLn $ reverse result

Box
   Dust
       Chips
            Chocolate
                     Monkeys
                            Geese

有时，根据您想要的计算形状，您可能希望使用 mapAccumL 而不是 mapAccumR，但您会明白。

另请注意，它是为 Traversable 实例定义的，而不仅仅是列表，因此它将适用于各种可遍历容器和数据结构，例如树、 map 、向量等。