List.Accumulate

官方说明：

使用accumulator从列表list中的项累积汇总值。
List.Accumulate(list as list, seed as any, accumulator as function) as any

解读：

如果已经学习过前面的List.TransformMany，应该已经对(x,y)=>这种双参数传递的形式有所了解。
而今天要讲的这个函数，也是这种形式，难度比transformmany再高一个档次，个人认为在所有函数中难度排top5。
但又是非常常用也非常好用的一个函数，尤其是用来解决一些算法的问题，是学习M语言入门到进阶之间的一道分水岭。
先来看语法，我的理解：List.Accumulate(迭代运算参考列表,迭代初始值,根据迭代运算参考列表进行迭代运算)

= List.Accumulate({1, 2, 3, 4, 5}, 0, (state, current) => state + current)。
这是最简单的累加，第三参数中的current表示第一参数中的list，state表示每一步计算的结果，初始值为第二参数。
第一步，将第二参数中的0作为初始值，取第一参数中的第一个元素1，代入第三参数中的表达式计算，0+1=1。
第二步，将第一步得到的结果1作为变量传递到state，取第二个元素2再次计算，1+2=3。
第三步，再将上一步得到的结果3作为变量传递到state，取第三个元素3再次计算，3+3=6。
......
一直循环迭代到最后一个值计算完成，返回最终的state，也就是1-5的求和，结果为15。
分解来看，就相当于定义一个fx=(state,current)=>state+current的函数，第一步取list中第一个元素调用fx(0,1)，第二步调用fx(fx(0,1),2)，循环嵌套fx(fx(fx()))......

这是官方给的案例，其中两个变量用了比较长的名字，我们在自己写的时候习惯用短一点的变量名，比如(s,c)=>或者(x,y)=>。
第二参数seed类型为any，也就是说初始值的类型不仅可以是上边的number，也可以是text,list,record等任意类型。

再举个例子= List.Accumulate({1..5},{},(x,y)=>x&{y})，初始值为空的list，将第一参数中的每一个元素依次取出来装进{}中。
就好比我有一瓶糖果，还有一个一模一样的空瓶，我现在把糖果一颗一颗取出来，并装到空瓶中。
最终原来的瓶子空了，但我又得到一瓶新的糖果。
在这个例子中，最终的结果和第一参数原来的list显然是一样的，我举这个例子是希望大家对整个计算过程能有个清晰的认识。

了解了基本语法，我们从10个案例来看这个函数具体有哪些应用？

案例1：批量替换

= List.Accumulate({"0".."9"},"畅心88,123,象山海鲜,10086,哆啦没有萌101",(x,y)=>Text.Replace(x,y,"a"))
把第二参数中文本里的所有数字，批量替换为"a"。
先取list中第一个元素完成第一次替换，将上一步替换的结果作为待替换值，取第二个元素再次替换，作用相当于嵌套10次Text.Replace。

当然替换值也不一定只是固定值，也可以是基于y的变形转换，比如在《M函数名词频统计》中有一个List.Accumulate({"A".."Z"},_,(x,y)=>Text.Replace(x,y,"."&y))的用法。
按照这个思路，我们只需要调整下第一参数的list结构，就可以实现每次替换为不同的值，比如把刚才文本中的"1"替换为"a"，"8"替换为"b"。
= List.Accumulate({{"1","a"},{"8","b"}},"畅心88,123,象山海鲜,10086,哆啦没有萌101",(x,y)=>Text.Replace(x,y{0},y{1}))

第一参数为list套list，每次替换取内层list中第一个元素，替换为第二个元素。

案例2：条件分组

成绩列表={62,59,10,45,78,99,100,18,65,84,23,76}，小于60的装入一个list，大于等于60的装入另一个list，各回各家各找各妈。
= List.Accumulate(成绩列表,{{},{}},(x,y)=>if y<60 then {x{0}&{y},x{1}} else {x{0},x{1}&{y}})
初始值给一个list，里面包含两个空的list，然后依次对第一参数中每一个传进来的参数进行判断，如果<60就装进第一个list，否则装进第二个list。

案例3：零钱兑换

我现在银行卡里还有58块7毛的巨款要提现，要求按照人民币面值从大到小的顺序给出兑换规则。
= List.Accumulate({100,50,20,10,5,1,0.5,0.1},{{},58.7},(x,y)=>{x{0}&{Number.IntegerDivide(x{1},y)},Number.Round(Number.Mod(x{1},y),2)}){0}
这个比较好理解，初始值为{{},58.7}，一个空list用来装钞票，另一个用来显示余额。
第一步传入100，取整=0，那就是0张100放进来，余额还是58.7；第二步传入50，取整=1，1张50放进来，余额还有8.7。
最后深化出第一个list，得到结果{0,1,0,0,1,3,1,2}。

案例4：向下填充逆过程

之前专门写过一篇介绍《向下填充逆过程》，这里再给一个使用acc的解法。
= List.Accumulate({"一年级","一年级","一年级","二年级","二年级"},{{},{}},(x,y)=>{x{0}&{if List.Last(x{1})=y then null else y},x{1}&{y}}){0}

这个情况稍微复杂点，我们慢慢来一步步分析，同样使用两个空的list作为容器，一个用来装载结果，一个用来装载已传递进来的元素。
第一步，x={{},{}}，y="一年级"，计算结果为{{"一年级"},{"一年级"}}。
第二步，x={{"一年级"},{"一年级"}}，y="一年级"，计算结果为{{"一年级",null},{"一年级","一年级"}}。
后面的步骤同理，因为第二个list装载的是已传递进来的元素，如果下一个传递进来的元素等于已传递元素列表中的最后一个，也就是上一个传递进来的元素，那么就返回null，否则返回本身，并装载在第一个list中。
最终的结果为{{"一年级",null,null,"二年级",null},{"一年级","一年级","一年级","二年级","二年级"}}，只要再用{0}深化出第一个list即为我们要的结果。

上面用的方法是每步把y装载到list中，但实际上在本题中不用装载而是直接引用每步的迭代值也可以，写成= List.Accumulate({"一年级","一年级","一年级","二年级","二年级"},{{},0},(x,y)=>{x{0}&{if x{1}=y then null else y},y}){0}
第二参数{{},0}中的0只是一个形式，只要是不等于"一年级"的任意值结果都一样。
这样写公式更简洁，但第一种写法更规范一些。

案例5：累计求和

累计求和算是老问题了，之前已经介绍过很多种不同的方法，当然用acc也是可以做的。
= List.Accumulate({1..9},{},(x,y)=>x&{List.Sum({List.Last(x),y})})
同样初始值用一个空的list，第一步代入1，返回{1}；第二步代入2，{1}&List.Sum({1,2})={1,3}；第三步代入3，{1,3}&List.Sum({3,3})={1,3,6}，依此类推。

案例6：斐波那契数列

= List.Accumulate({1..9},{1,1},(x,y)=>x&{List.Sum(List.LastN(x,2))})
初始值为{1,1}，第一步结果为{1,1,2}，第二步为{1,1,2,3}，每次取list中最后两个元素相加，并将结果装载进list中，最后的结果为{1,1,2,3,5,8,13,21,34,55,89}。
此时最右边表达式中并没有y，所以第一参数的list只起到控制循环次数的作用，换成任意一个包含9个元素的list结果都是一样。
这种借助其他函数的方法比较容易理解一些。再来看一个只用acc的写法：
= List.Accumulate({1..9},{1,1},(x,y)=>x&{x{y-1}+x{y}})
第一步x={1,1}，y=1，x{0}+x{1}=2；第二步x={1,1,2}，y=2，x{1}+x{2}=3。
随着每一步x增加一个元素，而y每次+1，x{y-1}和x{y}每次总能取到x中的最后两个元素，原理和上面其实是一样的。

案例7：约瑟夫环

把13个人围成一圈，从1开始报数，报到7杀掉然后下一位接着从1开始报，找最后一位幸存者。
通常约瑟夫环有两种解法，一种是数学解法，一种是模拟解法，此为效率更高的数学解法。公式看起来好像很简单，但是推导过程很难，有兴趣的话可以看下知乎的推导过程，三两句解释不清楚。
= List.Accumulate({1..13},0,(x,y)=>Number.Mod(x+7,y))+1

案例8：分组断点跳出

列表={8,5,9,5,6,7,8,7,4,5,6,4,5}，从第一个元素开始按顺序累加，累加结果<=20时分为一组，下一组往下重新累加，求共可以分为几组。 = List.Accumulate(列表,{0,1},(x,y)=>if x{0}+y<=20 then {x{0}+y,x{1}} else {y,x{1}+1}){1}
初始值为{0,1}，两个元素一个用来记录当前累加的结果以判断是否<=20，另一个用来记录组数。 第一步x={0,1},y=8，0+8=8<=20，所以得到{8,1}；第二步x={8,1},y=5,8+5=13<=20，得到{13,1}；第三步x={13,1},y=9，13+9=22>20，所以得到{9,2}。
后面依此类推，每当累加结果>20，前面的累加归零，并将第二个元素+1，所以最终再用{1}深化，即为组数。

案例9：压缩字符串

"AAABBCAACCC"压缩为"A3B2C1A2C3"。
= List.Accumulate(Text.ToList("AAABBCAACCC"&"0"),{"","",""},(x,y)=>if x{0}=y then {x{0},x{1}+1,x{2}} else {y,1,x{2}&x{0}&Text.From(x{1})}){2}
首先将字符串转成单字符列表，第二参数初始值为3个空文本。第1个文本接受每一步传递进来的元素，第2个文本记录连续重复次数，第3个文本负责将前两个文本合并输出。
第一步，x={"","",""},y="A"，""<>"A"，得到{"A",1,""}。
第二步，x={"A",1,""},y="A"，"A"="A"，得到{"A",2,""}，同理第三步得到{"A",3,""}。
第四步，x={"A",3,""},y="B"，"A"<>"B"，得到{"B",1,"A3"}。
再往下，如果碰到连续相同的，三个文本中第1和第3个都保持不变，而第2个每迭代一步就计数+1，一旦遇到不同的，就将前2个文本中记录的信息输出到第3个中。
但是到了最后一个字符"C"，此时的结果为{"C",3,"A3B2C1A2"}，所以要加一个任意不等于"C"的字符使其跳出循环，并将结果记录到第3个文本中，最终深化出{2}即为结果。

案例10：压缩连续数

将列表{1,2,7,9,10,11,13}压缩为{"1-2","7","9-11","13"}。

let
    源 = {1,2,7,9,10,11,13},
    压缩 = List.Accumulate(
	源&{0},
	[
		s="",
		e="",
		r={}
	],
	(x,y)=>if x[s]="" and x[e]="" 
		then [
			s=y,
			e=y,
			r={}
		] 
		else (
			if y-x[e]=1 
			then [
				s=x[s],
				e=y,
				r=x[r]
			] 
			else [
				s=y,
				e=y,
				r=x[r]& {
					Text.From(x[s])&(
						if x[s]=x[e] 
						then "" 
						else Text.From(-x[e])
					)
				}
			]
		)
    )[r]
in
    压缩

思路和上一题有点类似，但更繁琐一些。为了使过程更清晰，我缩进了代码，并将第二参数的容器换成了record。
初始值中有三个值，s表示start开始，用来装载每一段的起始值；e表示end结束，用来装载每一段的结尾值；r表示result，用来装载结果。
第一步，x=[s="",e="",r={}]，y=1，第一段if是针对起始值的特殊处理，返回[s=1,e=1,r={}]，后面的步骤全部只看第一个else后面的表达式。
第二步，x=[s=1,e=1,r={}],y=2，2-1=1，返回[s=1,e=2,r={}]。也就是当传入的y为连续的时候，s和r保持不变，只有e变成每一步传入的y值。
第三步，x=[s=1,e=2,r={}],y=7，7-1<>1，所以看第二个else后面的表达式，s和e同时变为每一步传入的y值，同时根据s和e组合成"s-e"的文本格式记录在r中，比如"1-2"。
但是如果s=e，也就是说只有一个连续的时候，比如"7"，我们不要"7-7"，所以&""进行特殊处理。
后面的步骤依此类推，遇到连续值就更新e，一旦遇到不连续的就保存到r中。
同上一题一样，对原列表结尾&{0}，使其强制跳出循环，最后深化出[r]即为结果。

附加题

在《先进先出分配法》中的解法3，当时只给了解法没有解释，学完了上面的10个案例再回头看就会容易很多。
核心代码为第三步的fx，自定义一个函数，l为分组后每个表中的[入库数]列，t为[库存]。
简化下题目，以分组后的产品A表为例，现有[库存]为200，[入库数]为{50,60,100,300,20,0,100}，按先进先出法分配。

= List.Accumulate({50,60,100,300,20,0,100},
		{{},0},
		(x,y)=>if x{1}+y<200
		       then {x{0}&{y},x{1}+y}
		       else {x{0}&{List.Max({200-x{1},0})},x{1}+y}
	){0}

初始值为{{},0}，{}用来装载分配结果，0用来记录累计入库数。
第一步，x={{},0}，y=50，0+50=50<200，返回{{50},50}。 第二步，x={{50},50}，y=60，50+60=110，返回{{50,60},110}。 也就是说只要累计入库数<库存数，那么每次都按照[入库数]全额入库，计划是入多少就入多少。 但是到了第三步，x={{50,60},110}，y=100，110+100>200，那么就要执行else，用库存的200减去累计入库数，得到剩余库存数分配给当期，所以第三步返回的结果为{{50,60,90},210}。
第四步，x={{50,60,90},210}，y=300，210+300=510>200，执行else，但是此时累计入库已经>200，再用200减就是负数，但剩余库存为0应该分配0才对，就要再对负数进行归零处理。
这里用了max和0比较最大值，正数就返回本身负数就返回0，和if>0是一个意思。
再后面的步骤，返回的结果那就都是0了，所以最终的结果为{{50,60,90,0,0,0,0},630}，深化出{0}即为先进先出分配法。

总结：

虽然官方文档里对acc的介绍只是一笔带过，但是如果展开讲得写十页纸，以上给的10个案例只是冰山一角。
这个函数已经是M语言中里相当难的了，一两遍看不懂很正常。但还不是最难的，因为后面还有个List.Generate要讲。
acc的难点不在第一参数，就是一个list，也不在第三参数，而是第二参数，因为第二参数搭建好以后，你就脑子里自然会考虑清楚处理逻辑。

 

练习：

现有各尺码库存表，若一个款号有连续4件库存大于0即为齐码，否则为断码。比如{5,3,12,0,0,11,6,2}，最大连续次数为3，即为断码。题目见附件。