函数式思维

2018-12-11 17:03:52 浏览数 (1)

自从大四看了三章《SICP》之后我就自诩为一个函数式编程爱好者，之前也在公司分享过一个 Haskell 的 Topic，效果非常糟糕，讲到后来已经没剩几个人了，只得草草收场。在写这篇文章的时候我突然想起来，之前还发过一个朋友圈，跟人论述我对范畴论一些概念的理解，翻了翻朋友圈找到了：

fp0.jpeg

fp1.jpeg

我自己读了一遍……

emm.jpeg

今天我们就讲点简单的吧，举个例子大概感受下函数式思维。

一道题

电话号码的字母组合

今天备战双十一，因为也没太多事情，就随便刷刷 leet code，看到了上题。

代码语言：javascript复制
/**
 * @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);

所以合起来就是这样的：

代码语言：javascript复制
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')); 输出是这样的：

代码语言：javascript复制
[ [ 'ad', 'bd', 'cd' ],
  [ 'ae', 'be', 'ce' ],
  [ 'af', 'bf', 'cf' ] ]

结果已经很接近了，只要把数组降维成一维数组就好，这主要是因为 letters[digit].map(mapper) 的 mapper 是一个返回值为数组的函数，我们只要用 letters[digit].flatMap(mapper) 就可以了，然而很遗憾 JS 居然还没完全支持 flatMap，只是个实验特性，那我们就自己实现一个，所以最终的代码是这样：

代码语言：javascript复制
/**
 * @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% 的用户。我看了下别人的答案，用三个循环：

代码语言：javascript复制
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）是没有副作用的（或者说隐藏了副作用），而真实的世界却充满副作用，为了能够正常工作并且保持自己的纯粹，它引入了范畴论中的各种概念，很有意思但确实有比较高的门槛，而且那些复杂的理论学了平常用不到很快就忘了（我就是这样……）。但函数式的思维，却是可以成为一种习惯，融入日常开发中的。

haskell git nat

0 人点赞