Reduce 和 Transduce 的含义

学习函数式编程,必须掌握很多术语,否则根本看不懂文档。

本文介绍两个基本术语:reducetransduce。它们非常重要,也非常有用。

一、reduce 的用法

reduce是一种数组运算,通常用于将数组的所有成员"累积"为一个值。

var arr = [1, 2, 3, 4]; var sum = (a, b) => a + b; arr.reduce(sum, 0) // 10

上面代码中,reduce对数组arr的每个成员执行sum函数。sum的参数a是累积变量,参数b是当前的数组成员。每次执行时,b会加到a,最后输出a

累积变量必须有一个初始值,上例是reduce函数的第二个参数0。如果省略该参数,那么初始值默认是数组的第一个成员。

var arr = [1, 2, 3, 4]; var sum = function (a, b) { console.log(a, b); return a + b; }; arr.reduce(sum) // => 10 // 1 2 // 3 3 // 6 4

上面代码中,reduce方法省略了初始值。通过sum函数里面的打印语句,可以看到累积变量每一次的变化。

总之,reduce方法提供了一种遍历手段,对数组所有成员进行"累积"处理。

二、map 是 reduce 的特例

累积变量的初始值也可以是一个数组。

var arr = [1, 2, 3, 4]; var handler = function (newArr, x) { newArr.push(x + 1); return newArr; }; arr.reduce(handler, []) // [2, 3, 4, 5]

上面代码中,累积变量的初始值是一个空数组,结果reduce就返回了一个新数组,等同于执行map方法,对原数组进行一次"变形"。下面是使用map改写上面的例子。

var arr = [1, 2, 3, 4]; var plusOne = x => x + 1; arr.map(plusOne) // [2, 3, 4, 5]

事实上,所有的map方法都可以基于reduce实现。

function map(f, arr) { return arr.reduce(function(result, x) { result.push(f(x)); return result; }, []); }

因此,map只是reduce的一种特例。

三、reduce的本质

本质上,reduce是三种运算的合成。

  • 遍历
  • 变形
  • 累积

还是来看上面的例子。

var arr = [1, 2, 3, 4]; var handler = function (newArr, x) { newArr.push(x + 1); return newArr; }; arr.reduce(handler, []) // [2, 3, 4, 5]

上面代码中,首先,reduce遍历了原数组,这是它能够取代map方法的根本原因;其次,reduce对原数组的每个成员进行了"变形"(上例是加1);最后,才是把它们累积起来(上例是push方法)。

四、 transduce 的含义

reduce包含了三种运算,因此非常有用。但也带来了一个问题:代码的复用性不高。在reduce里面,变形和累积是耦合的,不太容易拆分。

每次使用reduce,开发者往往都要从头写代码,重复实现很多基本功能,很难复用别人的代码。

var handler = function (newArr, x) { newArr.push(x + 1); return newArr; };

上面的这个处理函数,就很难用在其他场合。

有没有解决方法呢?回答是有的,就是把"变形"和"累积"这两种运算分开。如果reduce允许变形运算和累积运算分开,那么代码的复用性就会大大增加。这就是transduce方法的由来。

transduce这个名字来自 transform(变形)和 reduce 这两个单词的合成。它其实就是reduce方法的一种不那么耦合的写法。

// 变形运算 var plusOne = x => x + 1; // 累积运算 var append = function (newArr, x) { newArr.push(x); return newArr; }; R.transduce(R.map(plusOne), append, [], arr); // [2, 3, 4, 5]

上面代码中,plusOne是变形操作,append是累积操作。我使用了 Ramda 函数库transduce实现。可以看到,transduce就是将变形和累积从reduce拆分出来,其他并无不同。

五、transduce 的用法

transduce最大的好处,就是代码复用更容易。

var arr = [1, 2, 3, 4]; var append = function (newArr, x) { newArr.push(x); return newArr; }; // 示例一 var plusOne = x => x + 1; var square = x => x * x; R.transduce( R.map(R.pipe(plusOne, square)), append, [], arr ); // [4, 9, 16, 25] // 示例二 var isOdd = x => x % 2 === 1; R.transduce( R.pipe(R.filter(isOdd), R.map(square)), append, [], arr ); // [1, 9]

上面代码中,示例一是两个变形操作的合成,示例二是过滤操作与变形操作的合成。这两个例子都使用了 Pointfree 风格

可以看到,transduce非常有利于代码的复用,可以将一系列简单的、可复用的函数合成为复杂操作。作为练习,有兴趣的读者可以试试,使用reduce方法完成上面两个示例。你会发现,代码的复杂度和行数大大增加。

六、Transformer 对象

transduce函数的第一个参数是一个对象,称为 Transformer 对象(变形器)。前面例子中,R.map(plusOne)返回的就是一个 Transformer 对象。

事实上,任何一个对象只要遵守 Transformer 协议,就是 Transformer 对象。

var Map = function(f, xf) { return { "@@transducer/init": function() { return xf["@@transducer/init"](); }, "@@transducer/result": function(result) { return xf["@@transducer/result"](result); }, "@@transducer/step": function(result, input) { return xf["@@transducer/step"](result, f(input)); } }; };

上面代码中,Map函数返回的就是一个 Transformer 对象。它必须具有以下三个属性。

  • @@transducer/step:执行变形操作
  • @@transducer/init:返回初始值
  • @@transducer/result:返回变形后的最终值

所有符合这个协议的对象,都可以与其他 Transformer 对象合成,充当transduce函数的第一个参数。

因此,transduce函数的参数类型如下。

transduce( 变形器 : Object, 累积器 : Function, 初始值 : Any, 原始数组 : Array )

七、into 方法

最后,你也许发现了,前面所有示例使用的都是同一个累积器。

var append = function (newArr, x) { newArr.push(x); return newArr; };

上面代码的append函数是一个常见累积器。因此, Ramda 函数库提供了into方法,将它内置了。也就是说,into方法相当于默认提供appendtransduce函数。

R.transduce(R.map(R.add(1)), append, [], [1,2,3,4]); // 等同于 R.into([], R.map(R.add(1)), [1,2,3,4]);

上面代码中,into方法的第一个参数是初始值,第二个参数是变形器,第三个参数是原始数组,不需要提供累积器。

下面是另外一个例子。

R.into( [5, 6], R.pipe(R.take(2), R.map(R.add(1))), [1, 2, 3, 4] ) // [5, 6, 2, 3]

八、参考链接

(完)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

2392
来自专栏数据结构与算法

1200 同余方程

1200 同余方程 2012年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目...

2834
来自专栏人工智能LeadAI

讨厌算法的程序员 1 | 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生出一...

2977
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第五章 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦了...

3655
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第12章 pandas高级应用12.1 分类数据12.2 GroupBy高级应用12.3 链式编程技术12.4 总结

前面的章节关注于不同类型的数据规整流程和NumPy、pandas与其它库的特点。随着时间的发展,pandas发展出了更多适合高级用户的功能。本章就要深入学习pa...

6867
来自专栏TensorFlow从0到N

讨厌算法的程序员 1 - 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生...

3384
来自专栏玄魂工作室

Python数据结构与算法-在M个数中找K个最小的数

比如输入10,-9,0,100,90,1,4,-9;找到最小的3个数为:-9,-9,0

2191
来自专栏数据处理

动态规划

1054
来自专栏计算机视觉与深度学习基础

Leetcode 218. The Skyline Problem 线段树

A city's skyline is the outer contour of the silhouette formed by all the build...

3139
来自专栏Hongten

对于一个运行时间为100n*n的算法,要使其在同一台机器上,在比一个运行时间为2^n的算法运行的很快,n的最小值是多少

2033

扫码关注云+社区

领取腾讯云代金券