跳到主要内容

函数式编程基础

函数式编程建立在几个核心概念之上。理解这些概念是掌握函数式编程的关键。

纯函数​

纯函数是函数式编程的基石。一个函数是纯函数，当且仅当：

  1. 相同的输入总是产生相同的输出（确定性）
  2. 没有副作用（不影响外部状态）

示例​

// 纯函数
function add(a, b) {
    return a + b;
}

// 每次调用 add(2, 3) 总是返回 5
console.log(add(2, 3));  // 5
console.log(add(2, 3));  // 5

// 非纯函数（依赖外部状态）
let taxRate = 0.1;
function calculateTax(amount) {
    return amount * taxRate;  // 依赖外部变量 taxRate
}

// 非纯函数（有副作用）
function appendToList(item, list) {
    list.push(item);  // 修改了输入参数
    return list;
}

为什么纯函数重要？​

纯函数有以下优点：

  1. 易于测试：不需要复杂的测试环境
  2. 易于推理：函数的行为完全由输入决定
  3. 可缓存：相同输入可以缓存结果（记忆化）
  4. 可并行化：没有共享状态，天然支持并发
// 纯函数的缓存（记忆化）
function memoize(fn) {
    const cache = {};
    return function(...args) {
        const key = JSON.stringify(args);
        if (cache[key] !== undefined) {
            return cache[key];
        }
        const result = fn.apply(this, args);
        cache[key] = result;
        return result;
    };
}

// 缓存计算密集型函数
const memoizedAdd = memoize((a, b) => {
    console.log('计算中...');
    return a + b;
});

console.log(memoizedAdd(1, 2));  // 计算中... → 3
console.log(memoizedAdd(1, 2));  // 3（直接从缓存返回）

副作用​

副作用是指函数除了返回值之外，还对外部状态产生了影响。常见的副作用包括：

  • 修改全局变量或外部变量
  • 修改输入参数
  • 进行 I/O 操作（文件读写、网络请求）
  • 打印日志
  • 修改 DOM
  • 触发事件
// 有副作用的函数
let counter = 0;

function increment() {
    counter++;  // 修改外部状态
    console.log(counter);  // I/O 操作
    return counter;
}

// 无副作用的函数（纯函数）
function incrementPure(value) {
    return value + 1;
}

隔离副作用​

在实际应用中，副作用是不可避免的（程序需要与外部世界交互）。函数式编程通过将副作用隔离到特定区域来管理它们：

// 将副作用推到程序的边界
function processUserData(users) {
    // 纯函数部分：数据处理
    const filtered = users.filter(user => user.active);
    const sorted = filtered.sort((a, b) => a.name.localeCompare(b.name));
    const formatted = sorted.map(user => `${user.name} (${user.email})`);
    
    return formatted;
}

// 在边界处理副作用
function main() {
    // 获取数据（副作用）
    const users = fetchUsersFromAPI();
    
    // 处理数据（纯函数）
    const result = processUserData(users);
    
    // 输出结果（副作用）
    result.forEach(line => console.log(line));
}

引用透明​

引用透明是指一个表达式可以被它的值替换而不改变程序的行为。纯函数保证了引用透明。

// 引用透明示例
const result1 = add(2, 3) * 2;  // 10
const result2 = 5 * 2;          // 10（add(2, 3) 被替换为 5）

// 非引用透明
let x = 0;
function increment() {
    return ++x;
}

const result3 = increment() + increment();  // 3（1 + 2）
const result4 = 1 + 2;                      // 3（但行为不同）

不可变性​

不可变性是指数据一旦创建就不能被修改。在函数式编程中，我们通过创建新数据而不是修改现有数据来处理变化。

// 可变操作（非函数式）
const arr = [1, 2, 3];
arr.push(4);  // 修改了原数组
arr[0] = 0;   // 修改了原数组

// 不可变操作（函数式）
const original = [1, 2, 3];
const newArr = [...original, 4];  // 创建新数组
const modified = [0, ...original.slice(1)];  // 创建新数组

console.log(original);  // [1, 2, 3]（未改变）
console.log(newArr);    // [1, 2, 3, 4]
console.log(modified);  // [0, 2, 3]

Object.freeze 的局限​

Object.freeze 只能进行浅冻结，不能完全保证不可变性：

// 浅冻结
const frozen = Object.freeze({ name: '张三', address: { city: '北京' } });
frozen.name = '李四';  // 静默失败或报错（严格模式）
frozen.address.city = '上海';  // 可以修改！（嵌套对象未冻结）

// 深冻结函数
function deepFreeze(obj) {
    Object.keys(obj).forEach(key => {
        if (typeof obj[key] === 'object' && obj[key] !== null) {
            deepFreeze(obj[key]);
        }
    });
    return Object.freeze(obj);
}

一等函数​

在 JavaScript 中，函数是一等公民（First-class citizen），意味着函数可以：

  1. 被赋值给变量
  2. 作为参数传递
  3. 作为返回值返回
  4. 存储在数据结构中
// 函数赋值给变量
const greet = function(name) {
    return `你好，${name}！`;
};

// 函数作为参数
function callWithHello(fn) {
    return fn('Hello');
}

console.log(callWithHello(x => x.toUpperCase()));  // "HELLO"

// 函数作为返回值
function multiplier(factor) {
    return function(number) {
        return number * factor;
    };
}

const double = multiplier(2);
console.log(double(5));  // 10

// 函数存储在数组中
const operations = [
    x => x + 1,
    x => x * 2,
    x => x - 3
];

const result = operations.reduce((acc, fn) => fn(acc), 5);
console.log(result);  // ((5 + 1) * 2) - 3 = 9

高阶函数初探​

高阶函数是接收函数作为参数或返回函数的函数。JavaScript 内置了许多高阶函数：

// Array.prototype.map - 转换每个元素
const numbers = [1, 2, 3, 4, 5];
const doubled = numbers.map(x => x * 2);
console.log(doubled);  // [2, 4, 6, 8, 10]

// Array.prototype.filter - 过滤元素
const evens = numbers.filter(x => x % 2 === 0);
console.log(evens);  // [2, 4]

// Array.prototype.reduce - 累积计算
const sum = numbers.reduce((acc, x) => acc + x, 0);
console.log(sum);  // 15

// Array.prototype.find - 查找元素
const found = numbers.find(x => x > 3);
console.log(found);  // 4

函数组合示例​

函数组合是将多个函数组合在一起，形成一个新的函数：

// 简单的函数组合
const compose = (f, g) => x => f(g(x));

const addOne = x => x + 1;
const double = x => x * 2;

const doubleThenAddOne = compose(addOne, double);
console.log(doubleThenAddOne(5));  // 11（double(5) = 10，addOne(10) = 11）

// 管道（从左到右执行）
const pipe = (...fns) => x => fns.reduce((acc, fn) => fn(acc), x);

const transform = pipe(
    x => x + 1,
    x => x * 2,
    x => x - 3
);

console.log(transform(5));  // 9（5 + 1 = 6，6 * 2 = 12，12 - 3 = 9）

尾调用优化​

尾调用优化（Tail Call Optimization，TCO）是函数式编程中一个重要的优化技术，它允许递归函数在不增加调用栈的情况下执行，从而避免栈溢出错误。

什么是尾调用？​

尾调用是指一个函数的最后一步是调用另一个函数。根据 ECMAScript 规范，当函数的最后动作是调用另一个函数时，该调用就被称为尾调用。

// 尾调用示例
function foo(x) {
    return bar(x);  // 这是尾调用：bar 的返回值直接被 foo 返回
}

// 不是尾调用
function foo(x) {
    return bar(x) + 1;  // 不是尾调用：bar 调用后还需要 +1
}

function foo(x) {
    bar(x);  // 不是尾调用：隐式返回 undefined，不是返回 bar 的结果
}

为什么需要尾调用优化？​

在传统实现中，每次函数调用都会在调用栈上创建一个新的栈帧，保存函数的局部变量和返回地址。对于递归函数，如果递归深度很大，就会导致栈溢出：

// 没有 TCO 的递归：可能导致栈溢出
function factorial(n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // 不是尾递归：还需要乘以 n
}

// 测试
factorial(100000);  // RangeError: Maximum call stack size exceeded

尾调用优化的原理是：当函数的最后一步是调用另一个函数时，当前函数的栈帧可以被复用，不需要创建新的栈帧。这大大减少了内存使用。

尾递归​

尾递归是尾调用的一种特殊情况：函数在尾部调用自身。将普通递归转换为尾递归，需要使用"累加器"模式：

// 尾递归版本的阶乘函数
function factorial(n, acc = 1) {
    if (n <= 1) return acc;
    return factorial(n - 1, n * acc);  // 尾递归：直接返回递归调用的结果
}

console.log(factorial(5));  // 120
// 执行过程：
// factorial(5, 1)
// factorial(4, 5)
// factorial(3, 20)
// factorial(2, 60)
// factorial(1, 120) -> 返回 120

// 尾递归版本的斐波那契数列
function fibonacci(n, a = 0, b = 1) {
    if (n === 0) return a;
    if (n === 1) return b;
    return fibonacci(n - 1, b, a + b);
}

console.log(fibonacci(10));  // 55

尾递归转换技巧​

将普通递归转换为尾递归的关键是：将计算结果作为参数传递，而不是在返回时进行计算。

// 普通递归：求和
function sum(arr) {
    if (arr.length === 0) return 0;
    return arr[0] + sum(arr.slice(1));  // 不是尾递归
}

// 尾递归版本
function sumTail(arr, acc = 0) {
    if (arr.length === 0) return acc;
    return sumTail(arr.slice(1), acc + arr[0]);  // 尾递归
}

console.log(sumTail([1, 2, 3, 4, 5]));  // 15

// 普通递归：数组反转
function reverse(arr) {
    if (arr.length === 0) return [];
    return [...reverse(arr.slice(1)), arr[0]];  // 不是尾递归
}

// 尾递归版本
function reverseTail(arr, acc = []) {
    if (arr.length === 0) return acc;
    return reverseTail(arr.slice(1), [arr[0], ...acc]);
}

console.log(reverseTail([1, 2, 3, 4, 5]));  // [5, 4, 3, 2, 1]

JavaScript 中的支持情况​

ES6 规范包含了尾调用优化，但实际支持情况因引擎而异：

// 在支持 TCO 的环境中，这段代码可以正常运行
// 在不支持的环境中，会抛出栈溢出错误
function count(n) {
    if (n === 0) return 'done';
    return count(n - 1);  // 尾递归
}

// 测试环境是否支持 TCO
try {
    count(100000);  // 尝试大量递归
    console.log('当前环境支持尾调用优化');
} catch (e) {
    console.log('当前环境不支持尾调用优化');
}

重要提示：

  1. 必须使用严格模式：尾调用优化只在严格模式下生效，因为非严格模式下存在 arguments.callee 和 func.caller 等特性会干扰优化。
'use strict';  // 必须启用严格模式

function factorial(n, acc = 1) {
    if (n <= 1) return acc;
    return factorial(n - 1, n * acc);
}
  1. 浏览器支持情况：目前 Safari 是主流浏览器中唯一完整支持 TCO 的。Chrome 和 Firefox 出于调试和安全考虑，默认禁用了 TCO。

替代方案：蹦床函数​

在不支持 TCO 的环境中，可以使用"蹦床函数"（Trampoline）来安全地执行递归：

// 蹦床函数：将递归转换为循环
function trampoline(fn) {
    return function(...args) {
        let result = fn.apply(this, args);
        
        // 如果结果是函数，继续执行
        while (typeof result === 'function') {
            result = result();
        }
        
        return result;
    };
}

// 使用蹦床的阶乘函数
function factorialTrampoline(n, acc = 1) {
    if (n <= 1) return acc;
    // 返回一个函数而不是直接递归
    return () => factorialTrampoline(n - 1, n * acc);
}

const safeFactorial = trampoline(factorialTrampoline);
console.log(safeFactorial(100000));  // 安全执行，不会栈溢出

// 通用的蹦床包装器
function trampoline2(fn) {
    return (...args) => {
        let result = fn(...args);
        while (typeof result === 'function') {
            result = result();
        }
        return result;
    };
}

// 使用示例：安全的递归求和
function sumTrampoline(arr, acc = 0) {
    if (arr.length === 0) return acc;
    return () => sumTrampoline(arr.slice(1), acc + arr[0]);
}

const safeSum = trampoline2(sumTrampoline);
console.log(safeSum(Array(100000).fill(1)));  // 100000

尾递归的应用场景​

尾递归优化特别适合以下场景：

// 1. 树的遍历
function traverseTree(node, visit, acc = []) {
    if (!node) return acc;
    
    const newAcc = [...acc, visit(node)];
    
    // 先遍历左子树，再遍历右子树（尾递归形式）
    return traverseTree(
        node.right,
        visit,
        traverseTree(node.left, visit, newAcc)
    );
}

// 2. 查找操作
function findInList(list, predicate, index = 0) {
    if (index >= list.length) return null;
    if (predicate(list[index])) return list[index];
    return findInList(list, predicate, index + 1);
}

// 3. 累积计算
function reduceList(list, fn, acc, index = 0) {
    if (index >= list.length) return acc;
    return reduceList(list, fn, fn(acc, list[index]), index + 1);
}

const sum = reduceList([1, 2, 3, 4, 5], (a, b) => a + b, 0);
console.log(sum);  // 15

最佳实践​

  1. 优先使用迭代：在 JavaScript 中，由于 TCO 支持不完善，对于性能关键的场景，优先使用循环而不是递归。
// 推荐：使用迭代
function factorialIterative(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

// 如果需要函数式风格，使用蹦床
const factorial = trampoline(factorialTrampoline);

  1. 小规模递归使用普通递归：对于递归深度可控的场景，普通递归更直观。

  2. 注意严格模式：确保使用尾递归的代码运行在严格模式下。

小结​

本章我们学习了函数式编程的核心概念：

  1. 纯函数：相同输入产生相同输出，没有副作用
  2. 副作用：对外部状态的影响，需要隔离管理
  3. 引用透明：表达式可以被其值替换
  4. 不可变性：数据不可修改，通过创建新数据处理变化
  5. 一等函数：函数可以作为值传递
  6. 高阶函数：接收或返回函数的函数
  7. 函数组合：将小函数组合成复杂功能
  8. 尾调用优化：递归优化技术，避免栈溢出，需要严格模式支持

练习​

  1. 判断以下函数是否是纯函数，并说明原因：

    function square(x) {
        return x * x;
    }

    let total = 0;
    function addToTotal(x) {
        total += x;
        return total;
    }

  2. 使用纯函数重写以下函数：

    function appendAndSort(item, arr) {
        arr.push(item);
        return arr.sort();
    }

  3. 实现一个 pipe 函数，将多个函数从左到右组合。

  4. 使用 map、filter 和 reduce 计算数组中所有偶数的平方和。

  5. 将以下递归函数改写为尾递归形式：

    // 计算 1 到 n 的和
    function sumTo(n) {
        if (n <= 0) return 0;
        return n + sumTo(n - 1);
    }

    // 计算数组的最大值
    function findMax(arr) {
        if (arr.length === 1) return arr[0];
        const restMax = findMax(arr.slice(1));
        return arr[0] > restMax ? arr[0] : restMax;
    }