自从大四看了三章《SICP》之后我就自诩为一个函数式编程爱好者，之前也在公司分享过一个 Haskell 的 Topic，效果非常糟糕，讲到后来已经没剩几个人了，只得草草收场。在写这篇文章的时候我突然想起来，之前还发过一个朋友圈，跟人论述我对范畴论一些概念的理解，翻了翻朋友圈找到了：
fp0.jpeg
fp1.jpeg
我自己读了一遍……
emm.jpeg
今天我们就讲点简单的吧，举个例子大概感受下函数式思维。
一道题
今天备战双十一，因为也没太多事情，就随便刷刷 leet code，看到了上题。
/**
* @param {string} digits
* @return {string[]}
*/
const letterCombinations = function (digits) {
};
我的思路是这样的：
- 首先定义数字和字母的映射
const letters = [ [], [], ['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i'], ['j', 'k', 'l'], ['m', 'n', 'o',], ['p', 'q', 'r', 's'], ['t', 'u', 'v'], ['w', 'x', 'y', 'z'] ];- 传入的字符串可以看成是字符数组，而函数的返回值是个字符串数组，我的第一反应是做个 map 操作行不行? 但 map 操作其实是对每个元素做相同的映射，元素之间理应没有交互，而本题显然是要交互的，这种场景该用 reduce：
return digits.split('').reduce(append, ['']);- reduce 接受一个 append 函数，是个累积器，它接收两个参数，第一个参数是累积值（acc），第二个参数是数组的元素（数字，digit）。首先我们得取到数字对应的字母数组（letters[digit]），然后我们应该要对字母数组做一个 map 操作，把字母和累积值（也是个字母数组）中的元素组合起来，这样就涵盖了所有的组合情况：
const append = (acc, digit) => letters[digit].map(letter => acc.map(prefix => prefix + letter);
所以合起来就是这样的：
const letterCombinations = function (digits) {
if (!digits) return [];
const letters = [
[],
[],
['a', 'b', 'c'],
['d', 'e', 'f'],
['g', 'h', 'i'],
['j', 'k', 'l'],
['m', 'n', 'o',],
['p', 'q', 'r', 's'],
['t', 'u', 'v'],
['w', 'x', 'y', 'z']
];
return digits.split('').reduce((acc, digit) => letters[digit].map(letter => acc.map(prefix => prefix + letter)), ['']);
};
我们测一下，console.log(letterCombinations('23')); 输出是这样的：
[ [ 'ad', 'bd', 'cd' ],
[ 'ae', 'be', 'ce' ],
[ 'af', 'bf', 'cf' ] ]
结果已经很接近了，只要把数组降维成一维数组就好，这主要是因为 letters[digit].map(mapper) 的 mapper 是一个返回值为数组的函数，我们只要用 letters[digit].flatMap(mapper) 就可以了，然而很遗憾 JS 居然还没完全支持 flatMap，只是个实验特性，那我们就自己实现一个，所以最终的代码是这样：
/**
* @param {string} digits
* @return {string[]}
*/
Array.prototype.flatMap = function (func) {
return this.reduce((acc, x) => acc.concat(func(x)), []);
};
const letterCombinations = function (digits) {
if (!digits) return [];
const letters = [
[],
[],
['a', 'b', 'c'],
['d', 'e', 'f'],
['g', 'h', 'i'],
['j', 'k', 'l'],
['m', 'n', 'o',],
['p', 'q', 'r', 's'],
['t', 'u', 'v'],
['w', 'x', 'y', 'z']
];
// JS 的 flatMap 还是个实验特性，迷……
return digits.split('').reduce((acc, digit) => letters[digit].flatMap(letter => acc.map(prefix => prefix + letter)), ['']);
};
提交，通过，性能也还可以，超过 77% 的用户。我看了下别人的答案，用三个循环：
let letterCombinations = function(digits) {
if (digits === '') return [];
let dict = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
};
let res = [''];
for (let digit of digits) {
let len = res.length;
while (len-- > 0) {
let e = res.shift();
for (let c of dict[digit]) {
res.push(e + c);
}
}
}
return res;
};
其实效果是一样的，真的硬要说的话，Array 的 reduce 估计也是用循环实现的，所以我的解法底层可能也用了三个循环。但 reduce（Haskell 中的 fold）、map（fmap）、flatMap（bind）这三个函数其实是通用的模式，不止在数组中有用，要追本溯源的话可能又绕不开范畴论了，就不在这里多说了。
本文就是浅显地展示一下函数式编程的感觉，它可能是从更高层更抽象的角度出发，尽量不涉及中间状态，也不过早地沉入细节，而是理清思路之后通过函数间的组合来解决问题。真正的纯函数式语言（Haskell）是没有副作用的（或者说隐藏了副作用），而真实的世界却充满副作用，为了能够正常工作并且保持自己的纯粹，它引入了范畴论中的各种概念，很有意思但确实有比较高的门槛，而且那些复杂的理论学了平常用不到很快就忘了（我就是这样……）。但函数式的思维，却是可以成为一种习惯，融入日常开发中的。
网友评论