查看mapAccumR的工作原理 [英] Picture how mapAccumR works

查看:118
本文介绍了查看mapAccumR的工作原理的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

你能解释 mapAccumR 的工作原理,它解决的问题类型,以及它与 foldr 。我很难想象它是如何工作的。

解决方案

这是一个很好的问题。我希望这个文档有点更好。我最近自己也有一些用途,所以希望我能从一个人的角度来解释一下,他们在理解他们的工作方式时也有一些困难。

因此,类型签名是 mapAccumR 是:

可穿透t => (a→b→(a,c))→> a - > t b - > (a,tc)



让我们假设问题中的 Traversable 是一个列表因为它可能更容易理解这种方式,所以特化类型:

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



所以,为了解释这个, mapAccumR 是一个包含三个参数的函数(忽略currying,因为我们的解释很简单),我将在这里注释这些参数:

  mapAccumR ::(a  - > b  - >(a,c)) - > a  - > [b]  - > (a,[c])
mapAccumR :: mappingAndAccumulationFunction - > initialAccumulatorValue - > listToMapOver - >结果集合体和映射列表对

酷,所以清除一点一点有点混乱,对。那么它究竟做了什么?



好吧,它会创建一个累积映射:所以我们假设在第一步中,它的作用是将 initialAccumulatorValue listToMapOver 中的第一个 b ,并将它们传递给 mappingAndAccumulationFunction 函数,它将对它们做 something ,并返回两件事:1.一个新类型的值 a 和2.映射值以供稍后收集到映射列表中(请参阅类型resultAccumulatorAndMappedListPair )。这两个值是成对的,因此 mappingAndAccumulationFunction 的返回类型作为(a,c)



在第二步及后续步骤中,从上一步开始取(a,c)对,并将 c out并记住它,方法是将它追加到一个内部列表中,它将跟踪到最后,并将 a 拉出 mappingAndAccumulationFunction 的下一个应用程序的第一个参数,以及的下一个 b 值。 listToMapOver



一旦用完 b listToMapOver ,它返回一个具有最后一个值 a 的对和一个列表,其内容类型为 c



那么为什么你会想要这个功能呢?示例时间!

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

itemList = [鹅,猴子,巧克力,芯片]

> annotateLeastFavourites itemList
[4:鹅,3:猴子,2:巧克力,1:芯片]

或者,这可能会更简单一些:

 > mapAccumR(\ num item  - >(num + 1,show num ++:++ item))1 [鹅,猴子,巧克力,芯片] 
(5 ,[4:鹅,3:猴子,2:巧克力,1:芯片])

因此,我们可以看到,例如,在我们需要某些信息传递地图时,或者如果我们想要构建一个函数,它可以给我们一个累计值以及累计值集合值(右边),也需要传递每个步骤(左边的值)发生变化的信息。



也许你想得到最大值

 >一个项目列表的长度,您也可以用每个项目的长度对它们进行注释。 mapAccumR(\biggestSoFar item  - >(max largestSoFar(length item),(item,length item)))0 [鹅,猴子,巧克力,芯片] 
(9, [(鹅,5),(猴子,7),(巧克力,9),(芯片,5)])

这里有很多可能性。希望现在很清楚为什么人们说这就像是 map foldr 的组合。如果你碰巧像我一样几何思考,我认为它是当你需要变换某种集合的时候,并且你需要通过该集合中的一些变化的东西作为变换的一部分。



希望这有助于给你一个直觉,并在以后将这种模式存储在你的脑海中,以便以后当你认识到你将来可能需要它时:)

  let(_,result)= 
mapAccumR
(\累计长度项目 - >
let newLength = cumulativeLength +长度项目
in(newLength,take cumulativeLength(repeat'')++ item)

0
[鹅,猴子,巧克力,芯片,灰尘, 盒子]
在mapM_ putStrLn $倒转结果

盒子
尘埃
芯片
巧克力
猴子

有时候,根据你想要的计算形式,你会想要使用 mapAccumL 而不是 mapAccumR ,但是您会看到图片。



另外,请注意它是为 Traversable 实例定义的,而不仅仅是列表,所以它可以用于各种可遍历的容器和数据结构,例如Trees,Maps ,向量等。


Can you explain how exactly mapAccumR works, the kind of problems it solves,and how it's different from foldr. I have a hard time picturing how it works.

解决方案

This is a good question. I wish the documentation was a bit nicer around this. I recently had a use for them myself, so hopefully I can explain from the perspective of someone who also had some trouble understanding how they worked.

So, the type signature of mapAccumR is:

Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)

Let's just assume the Traversable under question is a list because it's possibly a bit easier to understand that way, so specialising the types:

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

So, to explain this, mapAccumR is a function of three arguments (ignoring currying, as we do for easy explanation), and I'm going to annotate these arguments here:

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

Cool, so that clears things a little bit, but it's still a bit confusing, right. So what the heck does it do?

Well, it does an accumulating map: so let's say in the first step, what it does is take the initialAccumulatorValue and the first b from the listToMapOver, and passes those to the mappingAndAccumulationFunction function, which will do something with them and return two things: 1. a new value of type a and 2. a mapped value for later collection into the mapped list (see the type of resultantAccumulatorAndMappedListPair). These two values are paired, hence the return type of the mappingAndAccumulationFunction function as (a, c).

In the second and subsequent steps, it takes this (a, c) pair from the last step, pulls the c out and remembers it by appending it to an internal list it's keeping track of until the end, and pulls the a out as the first argument to the next application of the mappingAndAccumulationFunction along with the next b value of the listToMapOver.

Once it runs out of b values from listToMapOver, it returns a pair which has the last value of a and a list whose contents are of type c.

So why the heck would you want this function? Example time!

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"]

or, maybe this is a bit simpler to see what's going on:

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

So we can see that it's a function that can give us a "cumulative value" along with our accumulating value anytime we need some information to pass along a map, for example, or if we want to build up a collection value (on the right) that also needs to have information passed along that changes with each step (the value on the left).

Maybe you want to get the max length of a list of items as you also annotate them with each item's length

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

There are lots of possibilities here. Hopefully now it's clear why people say this is like a combination of map and foldr. If you happen to think geometrically as I do, I think of it as when you need to transform a collection of some kind, and you need to thread some changing thing through that collection as part of the transformation.

Hope this has helped give you an intuition and store the pattern in your mind for later when you recognise you might need it in the future :)

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

Sometimes, and depending on the shape of the computation you want, you'd want to use mapAccumL instead of mapAccumR, but you get the picture.

Also, note that it's defined for Traversable instances, not just lists, so it will work on all sorts of traversable containers and data structures such as Trees, Maps, Vectors, etc.

这篇关于查看mapAccumR的工作原理的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆