Name: Password: Sign in
Javascript 中的文章
  • Javascript 的原型继承
  • React Native Practice
  • Javascript 中的函数式编程
  • 本文在 署名-非商业性使用-相同方式共享 3.0 版权协议下发布, 转载请注明出自 kyleslight.net

    Javascript 中的函数式编程

    1. 函数式编程

    函数式编程(Functional Programming,FP)是一种编程范式(或者说构建程序的风格),它的主要想法是像数学演算(起源于 λ calculus)一样去实现计算而避免改变数据状态;怎么理解这一点呢?比如对于洛伦兹变换:

    L=L01V2C2

    运动长度 L 只取决于 V 这个变量(L0C 为常量),我们可以很好地度量随着速度的变化运动长度如何变化;数学演算也涉及多个变量,但演算的过程中我们对它们的关系却非常确定,即几个独立的自变量改变将如何得到因变量。

    这种确定性给我们以启发:编程中的复杂性很大程度来源于状态的不确定;OOP 通过封装状态,只对信任的部分暴露内部状态来解决状态不确定的问题;而 FP 则通过完全消灭可变(mutable)状态来解决。

    2. 可变状态与不可变状态

    可变数据是造成状态不确定的原因。

    const fib = (n) => {
        let a = 1;
        let b = 1;
        let i;
        let temp;
    
        if (n <= 2) return 1;
        for (i = 3; i <= n; i++) {
            temp = a;
            a = b;
            b = a + temp;
        }
    
        return b;
    };
    

    这是递推的斐波那契数算法的一种实现,它包含了 4 个可变的状态(保存前两项计算结果的 a, b,用于控制循环次数的迭代下标 i 和中间变量 temp);这虽然是一个简单的算法,可对我们的大脑来说,在循环进行到任意一步时,我们都需要时刻关注下标是多少,有没有超过上界;以及当前循环进行完之后,两个保存结果的变量有没有得到符合我们预期的值(迭代向后进行了一位);

    这样一个看上去简单的算法在计算的过程中随时都在改变状态,除非仔细分析代码,否则我们很难说出在计算到某一步时此时的状态是什么。当真实的场景中存在更多时刻变化的数据时,我们的思维更容易陷入混乱,无法去很好地整理思路。

    既然可变状态这么可怕,我们可以消灭可变数据(mutable data),下面是等价的算法:

    const fib = (n) => {
        const move = ([a, b]) => [b, a + b];
        const rec = (m, a) => m > n ? a : rec(m + 1, move(a));
    
        const [l, r] = rec(3, [1, 1]);
        return r;
    };
    

    程序进行到任何一步,产生的都是不可变数据(immutable data),即状态都是确定的。

    3. 可变状态是如何被消灭的

    仔细思考,我们是如何实现 mutable data 到 immutable data 转变的呢?

    观察上面的例子:

    temp = a;
    a = b;
    b = a + temp;
    
    ([a, b]) => [b, a + b]
    

    在第一个例子中,我们为了暂存 a 的原始值创建了中间变量 temp,然后对 a 本身的值做了修改,再对 b 的值做了修改;我们这样理解变量:一个 容纳数据 的空间,在这个空间中数据可以根据需要 随时被替换

    在第二个例子中,我们并没有对形参做任何修改,我们将其作为另一个表达式的组成部分。我们这么理解变量:一个占据了 固定 值的空间,其他空间的值可以被该空间值 计算 得到,但无法对该空间的值做任何 替换 操作;

    换言之,数据之间只存在 映射,不存在 替换 关系。既然数据在函数式的观点里并不能做任何替换的操作,也就不可能可变。

    4. 函数

    既然数据之间只存在映射,那么我们需要一种方式去表达这种映射关系。数学演算已经给我们一个非常好的启发:这个映射就是函数。

    4.1 纯函数

    但是,如果只是像普通的语法那样去使用函数,并无法保证数据之间只存在简单的映射关系。例如:

    let pi = 3.1415926;
    
    const getCircleArea(r) => {
        // unexpected assignment like pi++
        return pi * r * r;
    };
    

    这个例子里,我们想要的 A(r)=πr2 并不能按照我们期望的方式运行。特别的,当我们反复调用这个函数,每次的返回会不一致。

    所以我们引入了纯函数(Pure Function)这个概念。

    纯函数是没有(Memory & I/O) side effect 的函数,它有很多性质,其中最重要的一条是:

    函数在被调用时不会对外界有 side effect(这意味着外层作用域的数据不会被改变),参数本身不会被改变;上面两个因素决定了返回值唯一取决于参数;从而使用相同的参数调用一定可以得到相同的结果。

    由于上述特性,纯函数非常利于调试 & unit test,因为你完全可以对这个函数进行反复测试并期望结果一致。而且正是由于这个特性,使用者可以将纯函数作为一个绝对靠谱的黑盒来使用,完全不用担心对外界的影响。只要保证映射关系不变,黑盒实现者可以对内部做任意优化而不用担心别人使用上会遇到问题。

    4.2 纯函数式控制流

    既然纯函数式语言里没有可变变量,那么我们如何表达类似循环这样的控制流呢?

    可以仔细体会一下循环是什么:循环是在满足某个终止条件前反复做某件事;一般而言,为了让每次循环后更加靠近终止条件,在每次循环时还会包含一个子过程,在这个子过程里做一点迭代这类微小的操作。

    如果你熟悉递归的定义的话,应该可以马上猜到了一类特殊的递归可以用来实现循环,例如:

    const rec = (i) => {
        if (i < 0) return;
    
        // do something
        rec(i - 1);
    };
    

    上面这种递归称作尾递归(Tail Recursion),与循环等价。

    当然递归是一种非常强大的表现方式,不仅可以实现简单的 Iteration,还可以用来处理表,树这样的数据结构。所有的这一切都可以使用纯函数自己的方式来解决。

    4.3 作为一等公民的函数与高阶函数

    如果函数不能像普通的参数那样被对待,那么它在表达一些概念上会受到限制;例如下面是对数组的每一个元素进行遍历的过程:

    const arr = [1, 2, 3];
    
    for (let i = 0; i < arr.length; i++) {
        const currentItem = arr[i];
        // do something for currentItem
    }
    

    我们观察到,当处理越来越多的遍历的时候,多数的处理都遵循了这样一个模式:

    • 找一个容器作为下标值,初始值为 0
    • 每次循环自增 1
    • 同时边界条件永远是数组 length - 1
    • 在循环的内部开始一定要暂存遍历的当前值

    既然这个套路如此固定,我们为什么不能将 遍历 这个过程本身作为一种抽象,当一次实现这种抽象之后,之后只需 focus 在循环真正想做的操作上,而不用关心如何处理遍历中的细节呢?

    让我们此刻假设函数不能作为普通参数被传递,那么关于

    • 如何遍历
    • 如何操作单个元素

    这两件事情将没办法分开处理,换句话说,我们无法实现对过程的抽象。

    解决方案是将函数看作一种普通的参数,我们可以把解决一类问题的过程抽象出来单独放在一个函数里(在这个例子中是遍历),这个函数接受函数作为参数,这个参数描述了该如何处理当前参数。

    例如处理遍历的函数,我们可以在某个地方单独定义:

    Array.prototype.myForEach = function(itemHandler) {
        const self = this;
    
        for (let i = 0; i < self.length; i++) {
            const currentItem = self[i];
            itemHandler(currentItem, i, self);
        }
    };
    

    那么之后在使用时,只需:

    const arr = [1, 2, 3];
    
    arr.myForEach((item, index, array) => {
        // handle your item
    });
    

    focus 在我需要处理的部分即可。

    在数学中,我们把接受函数作为参数或返回值为函数的函数称为 高阶函数(High-Order Function)。类似于求导(例如一阶求导算子 (x) )就是一个输入是函数,输出也是函数的高阶函数。在 CS 中,我们把将函数作为输入输出值的这种语言特性叫做“函数作为一等公民 ( treats functions as first-class citizens)”。

    4.4 柯里化

    柯里化(Currying)是一种将多参数的函数转变为单一参数函数的技术。通过将:

    const func = (arg1, arg2, arg3...) => {
        // handle args
    };
    

    转化为

    const func = (arg1) => {
        return (arg2) => {
            return (arg3) => {
                // ...
            };
        };
    };
    

    实现每次只固定一个参数。柯里化的一个典型的例子是 Angular 的 $filter,通过调用单一参数返回对应的 filter 函数。

    不过这个特性主要是用来做理论研究,多参数更符合目前实际使用习惯。

    5. 在 Javascript 中玩耍

    Javascript 的设计本身受到了 Scheme(Lisp 的方言)的影响,所以你可以在 Javascript 的各处看到函数式的影子,典型的如天生支持高阶函数,Lambda 表达式(匿名函数),将 callback 参数作为调用完毕后执行的钩子。所以接下来我们会探讨如何在 Javascript 中玩耍函数式。

    5.1 更加函数式的风格

    首先,观察自己代码是否有不必要的可变状态;例如:

    let a = 0;
    
    if (cond) {
        a = 1;
    } else {
        a = 2;
    }
    

    这类可以被优化为

    const a = cond ? 1 : 2;
    

    即多数 if/else 控制流导致的可变状态本质都可以转变成声名式的语句。

    另一个例子:

    let sum = 0;
    
    arr.forEach((item) => {
        sum += item;
    });
    

    在迭代中依次累计的操作可以被优化为

    const sum = arr.reduce((acc, cur) => (acc + cur), 0);
    

    通过尽可能一次性赋值来避免后续产生 mutable data 的机会。

    5.2 过程处理

    就如同我们之前探讨的,函数式可以较为方便地实现对过程的抽象。例如之前的例子,通过将关注点分离,调用函数的人可以更加专注于代码中易于变化的部分。

    Javascript 的标准 built-in Object 有非常多已经抽象好的高阶函数,而且很多我们已经在使用了。例如下面是 Array 原型上的函数:

    • every
    • filter
    • find
    • findIndex
    • forEach
    • map
    • reduce
    • some
    • sort

    是一些高阶函数,已经为我们造好了常用模式的轮子,它们都可以把比较 customized 的操作封装到它的函数参数里。

    另一个典型的例子是 Promise,对于 Promise 实例,它的 then 方法是一个高阶函数,接收两个参数:

    p.then(
        onFulfilled,
        onRejected
    );
    

    在被 resolvereject 时分别被执行。这同样是一个将关注点分离的抽象技术。通过这一层抽象,使用者不用关心如何去维护成功与失败的调用链,只需要 focus 在如何处理当前成功或失败时该做什么即可。

    5.3 数据结构处理

    在纯函数式的语言里,实现数据结构更加优雅与简洁:数据之间的组合是简单的映射关系。这样我们可以非常方便地实现对数据结构的操作。

    例如:

    const arr = [1, 114, 32122];
    const oddArr = arr.filter(n => n % 2 === 1);
    

    就完成了对数组的映射,它的结果得到了符合我们期望的新数组。

    沿着这个想法,我们可以将各个映射像电子元件一样一层一层组合起来,操作复杂的数据结构。

    下面是我们面试中的一个问题:

    const menu = {
        label: 'Title',
        nodes: [{
            label: 'Section 1',
            nodes: [{
                label: 'Subsection 1-1',
                nodes: [{
                    label: 'Subsubsection 1-1-1',
                    nodes: []
                }, {
                    label: 'Subsubsection 1-1-2',
                    nodes: []
                }]
            }, {
                label: 'Subsection 1-2',
                nodes: [{
                    label: 'Subsubsection 1-2-1',
                    nodes: []
                }]
            }]
        }, {
            label: 'Section 2',
            nodes: [{
                label: 'Subsection 2-1',
                nodes: []
            }]
        }]
    };
    
    const converter = () => {
        // TODO
    };
    
    // Expected Output
    // Title
    //     Section 1
    //         Subsection 1-1
    //             Subsubsection 1-1-1
    //             Subsubsection 1-1-2
    //         Subsection 1-2
    //             Subsubsection 1-2-1
    //     Section 2
    //         Subsection 2-1
    

    以及它的一个解法:

    const converter = (input) => (
        (function getLevelSeq(tree, level) {
            if (tree.nodes.length > 0) {
                return [{
                    label: tree.label,
                    level: level++
                }].concat(
                    tree.nodes
                        .map((item) => (getLevelSeq(item, level)))
                        .reduce((result, item) => (result.concat(item)), [])
                );
            }
    
            return {
                label: tree.label,
                level: level++
            };
        })(input, 0)
            .map((levelItem) => {
                const indent = (new Array(levelItem.level).fill('    ')).join('');
                return `${indent}${levelItem.label}`;
            })
            .join('\n')
    );
    

    5.4 Functional Reactive Programming

    在命令式语言中,我们如果进行如下的赋值:

    a := b + c
    

    那么当 b 变化的时候,a 并不会相应有任何改变,这当然是符合预期的。但是在事件驱动的系统里,b 可能随时发生变化,而一个经常性的操作是 update a;如果一个系统有多个自发会变化的量存在,那么维护 update 的成本将会非常巨大。

    将这个问题延伸开来,如果要实现视图的更新( V := F(M)) ,也会是一件非常繁琐的事情。

    正因此,前端探索出了 MVVM 模式,通过 V := VM(M) 来自动处理 Update View 这样的事情。更彻底的例如 Vue 的 computed 属性能表达状态之间的映射关系。这样我们只需维护系统中的独立变量,所有其他被映射的状态都会被自动处理。

    FRP 也是我们正在使用的开发模式。

    5.5 如何取舍

    当然,FP 并不是没有弊端的,最主要的是空间利用效率的问题。如果一份空间存储的值被固定,那么做一些简单的 update 将不得不开辟新的空间(对于数组与更复杂的数据结构也一样),这需要消耗额外的时间与空间资源,在对性能要求极高的场合是不太适用的。

    另一方面,由于函数式的处理极度依赖递归,如果使用不当容易导致过深的递归调用,造成调用栈的溢出。

    在 Javascript 中,面对现实的场景,我们可以更加灵活地采用混合模式,取不同模式的优点。

    6. Summary

    函数式有非常多理念,其中最有用的莫过于关注执行结果而非执行过程本身。这样一种想法使得它可以相对于过程式和面向对象更轻易地组合代码块,构建起项目而不用过多担心这些代码块之间是否会互相影响(这几乎是 Software Engineering 的理想)。人更应该关注的是代码如何被简单、易用地组合。

    Copyright (c) 2014-2016 Kyles Light.
    Powered by Tornado.
    鄂 ICP 备 15003296 号