javascript中的reduce,fold和unfold

javascript/jquery

浏览数:60

2020-5-23

AD:资源代下载服务

好久没有写文章了,这次来谈谈foldunfold
PS:其实一直也没中断fp的学习,最近学了不少Ramda, Monad, Functor的相关知识,已经开始在项目中运用了,后续会一点点把实战和心得总结出来。

fold(reduce

说说reduce吧, 很喜欢这个函数,节省了不少代码量,而且有一些声明式的雏形了,一些常见的工具函数,flattendeepCopymergeDeep等用reduce实现的很优雅简洁。reduce也称为fold,本质上就是一个折叠数组的过程,把数组中的多个值经过运算变成一个值,每次运算都会有一个函数处理,这个函数就是reduce的核心元素,称之为reducerreducer函数是个2元函数,返回1个单值,常见的add函数就是reducer

const addReducer = (x, y) => x + y;

这个add函数就是一个reducer,最常见的用法就是结合数组的reduce方法来用

[1, 2, 3, 4, 5].reduce(addReducer, 0)  // 15

为了更好的理解reduce,下面用不同的思路实现一遍这个函数

使用for...of

const reduce = (f, init, arr) => {
  let acc = init;
  for (const item of arr) {
    acc = f(acc, item);
  }
  return acc
}
// 执行
reduceFor(addReducer, 0, [1, 2, 3, 4, 5])  // 15

使用while循环

reduce = (f, init, arr) => {
  let acc = init;
  let current;
  let i = 0;
  while ((current = arr[i++])) {
    acc = f(acc, current);
  }
  return acc;
}

// 执行
reduceFor(addReducer, 0, [1, 2, 3, 4, 5])  // 15

更像fold的实现

上面的实现也都好理解,但好像没有体现出来折叠(fold)这个过程,折叠应该是对数组的层层挤压操作,上面的实现数组和逻辑其实是分开了,而且也引入了比较多的中间变量,虽然是在内部没有副作用吧。
其实换个思路想一下,如果把状态通过参数来传递,就可以更好的体现fold的过程,这里的参数是值是指逐渐变化的数组和计算值,并可以尽可能的做到无状态,真正纯函数的实现是没有表达式,只有语句的,这个可以用递归做到。下面的实现是用尾递归实现的reduce,可以在实现的过程中就看出数组和计算值是怎样变化的。非常符合fold这个称谓

function reduce(f, init, arr) {
  if (arr.length === 0) return init;
  const [head, ...rest] = arr;
  return reduce(f, f(init, head), rest);
}

// 执行
reduce(addReducer, 0, [1, 2, 3, 4, 5])  // 15

unfold

fold反过来就是unfold, unfold顾名思义就是根据一个反过来的reducer,来生成一系列的值。此时这个如果说原来的reducer实现类似于(a, b) -> c,那反过来就是c -> [a, b], 生成序列是一个很基本的操作,但就是这个基本的操作,也有很多实现的思路,在介绍unfold之前,看一下实现序列的其他方法,最后来做一个对比。

序列的实现

range(0, 100, 5)

期待结果

[0, 5, 10, ... 95]

数组实现

这个就不多说了,大家应该都知道。

range = (first, last, step) => {
  const n = (last - first) / step + 1;
  return Array.from({ length: n - 1 })
            .map((_, index) => first + index * step);
}
// 也可以使用from的第二个参数
// Array.from({ length: n }, (_, i) => first + i * step);

生成器实现

生成序列还有一个利器,那就是generator,生成器生成器,就是用来生成数据的。generator返回一个迭代器,也很容易生成序列

function* range(first, last, step) {
  let acc = first;
  while (acc < last) {
    yield acc;
    acc = acc + step;
  }
}
[...range(0, 100, 5)]

两者相比,generator更注重生成的过程,Array注重数据变化的过程。

unfold实现

在实现unfold之前,首先梳理一下实现思路,和fold一样,也是用递归,且要在实现的过程中看到对应数据的变化。大体过程如下
0 -> [0, 5]
5 -> [5, 10]
10 -> [10, 15]
15 -> [15, 20]
...
90 -> [90, 95]
95 -> [95, 100]
可以看出过程恰恰是fold反过来,符合c -> [a, b]因为初始值肯定为一个数组,所以unfold只需要两个参数,实现如下。

function unfold(f, init) {
  const g = (f, next, acc) => {
    const result = f(next);
    const [head, last] = result || [];
    console.log(last);
    return result ? g(f, last, acc.concat(head)) : acc;
  };
  return g(f, init, []);
}

range = R.curry((first, last, step) =>
  unfold(next => next < last && [next, next + step], 0)
)

// 执行
range(0, 100, 5)

总结

以上就是结合reduce和一个生成序列的例子简单介绍了一下foldunfold这两个在fp编程中很重要的概念,当然他们功能不只是生成序列,还有很多很强大的功能,我们下一篇文章会具体介绍。

参考文档

如何在 JS 代码中消灭 for 循环

作者:dongzhe3917875