函数式思维

阅读 946
收藏 28
2018-11-10
原文链接:www.jianshu.com

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

评论