Marvin's Blog

在命令式编程领域, 函数的作用是代码复用, 抽象和封装, 实际上函数在所有的编程范式中都发挥了这些重要的作用. 函数式编程只是进一步将函数在编程中的角色从重要的手段升级为基础和本质. lambda 演算作为其理论基础, 显示了函数在计算领域的可能性和灵活性.

函数是一等公民

在函数式编程的标准中, 函数是一等公民的概念是基本的, 这里的一等公民也称为一等值(first-class), 其是编程语言中值的通用修饰词, 只要某个值满足以下3个条件, 就能被称为一等值:

可以作为参数传递给函数
可以作为函数的返回值
可以被赋值给变量

如果仅满足第一条, 则称为二等值, 如果3条都不满足, 则称为3等值. 例如 Label 在支持它的语言中基本都是3等值(只能用于 goto 等语句, 不能作为参数传递给函数等). 此外函数式编程从原则上排斥状态, 不鼓励使用变量, 纯粹的函数式编程语言中甚至没有变量, 因而在这些语言中, 第三个条件就变成了: 可以被赋值给常量

函数参数

函数可以作为参数传递, 这个最常见的就是时间处理函数了, 假如进行事件驱动编程时使用的语言不支持这一点，就必须将函数包装在其他某种能作为参数传递的值中. 这样包装事件处理函数不仅使代码更冗赘, 还会造成一些不便

数组的迭代方法

我们将函数作为参数传递的另一种经验来自于数组的迭代方法, 受到其他编程语言中数组列表之类的数据结构和 prototype, underscore 等脚本的启发, es5 给数组新增了一系列的迭代方法(Iterative methods), 如 map, reduce, filter等, 它们的参数中都有一个函数, 在对数组迭代时应用于每一个元素. 下面用函数的形式来表示这些方法:

map :: ((a → b), [a]) → [b]

reduce :: ((a, b) → a), a, [b]) → a

filter :: ((a → Boolean), [a]) → [a]

通过函数的类型可以看出, 被调用方法的数组变成了函数的第一个参数, 数组是最后一个形式参数, 而不像命令式风格作为第一个参数, 下面是使用这些函数的例子:

// 将一个数组中的字符串都变成大写
f.log(f.map(word => word.toUpperCase(), ['foo', 'bar']))
// 获取一个数组中每个字符串的长度
f.log(f.map(word => word.length, ['four', 'five', 'seven']))
// 获取一个数组中每个数的平方
f.log(f.map(n => n * n, [1,2,3,4,5])
// 将一个数组中的数字求和
f.log(f.reduce((accum, cur) => f.add(accum, cur), 0, nums))
// 获取一个数组中的奇数
f.log(f.filter(n => n % 2 !== 0, nums))

这些函数更有利于各自适用问题的解决, 假设没有它们, 而以命令式编程的方式来实现上述算法, 每一个例子都不可能用一行代码完成. 这些函数体现了函数作为参数传递的价值—传递函数就是传递和复用算法. 一个函数能够从参数中动态获取它要调用的函数, 既增强了调用函数行为的灵活性, 也扩大了被调用函数代码复用的可能性.

设计函数参数

以同样的思路, 我们还能定义数组迭代方法中没有的其他函数, 假设我们要求一个数组元素中的最大值, 元素为数字时, 可以直接调用 Math.max 方法, 那么元素为字符串时呢?, 最简单的是定义一个参数为字符串数组的求最大值的函数, 但数组的元素还可能是其他数据类型, 例如包含姓名, 年龄等属性的对象. 因此最通用的解决方案是定义一个接收函数参数的 max 函数, 该函数参数 fn 包含如何根据另一个数组参数的元素数据类型求最大值的信息. 如何设计这个函数参数的功能和相应的 max 如何利用它, 是十分值得考量的. 第一种思路是在 max 函数内对数组的元素两两比较大小. 如果数组中的元素为该函数支持的数据类型, 就直接进行比较, 否则需进行类型转换. 所以 fn 发挥的是将一个值映射为另一个值的作用:

const persons = [{name: 'larry', age: 12}, {name: 'Tom', age: 13}, {name: 'bob', age: 14}]
function maxByMap(map, list) {
	function select(a, b) {
		return f.gt(map(a), map(b)) ? a : b;
	}
	
	return f.reduce(select, undefined, list);
}

// 数组中的元素本身能比较大小的时候, 无需任何转换, 所以采用 identity 函数, 它简单返回参数值
f.log(maxByMap(f.identity, nums))

第二种思路是将比较大小的算法从 max 函数中抽离出来, 普遍的做法是通过一个比较函数 compare 来表达某个有序集合中元素的次序. 该函数接收两个参数, 当前者的次序高于后者时, 返回某个正数, 当前者的次序等于后者时, 返回0. 当前者的次序低于后者时返回某个负数:

function maxByCompare(compare, list) {
	function select(a, b) {
		return f.gt(compare(a, b), 0) ? a : b;
	}

	return list.reduce(select)	
}

f.log(maxByCompare(f.sub, [1,2,3,4,5]));
// 5

可以看出 compare 函数提供的信息对于当前问题有些多余, 找出最大值只需要确定两个值中较大的一个, 至于是大于还是大于等于则无需区分. 实际上 compare 函数最适合的场合是排序, 因为在那里大于或小于关系意味着要切换两个元素的位置, 等于则不需要. 延续这种思路, 我们只需要抽离出 gt 函数, 确定大小.

function maxByGT(gt, list) {
	function select(a, b) {
		return gt(a, b) ? a : b;
	}
}

f.log(maxByGT(f.gt, [1,2,3,4,5]));

以上 3 种思路有一个共同点, 就是利用函数参数构造出一个从两个值中选出较大值的 select 函数, 再将它传递给数组的 reduce 方法, 以冒泡算法找出最大值. 更进一步, 则直接传递 select 函数:

function maxBySelect(select, list) {
	return list.reduce(select)
}

函数返回值

相较于作为参数, 函数能作为返回值, 对编程语言的要求更高. 首先, 语言要支持函数的嵌套声明, 即能在一个函数内声明另一个函数, 其次, 假如返回的函数都要提前声明, 是很不方便的, 更便利的做法是就地创建返回的函数, 这要求语言支持运行时创建新的函数值, 就像运行时能创建新的数字值, 字符串值等一样, 实际上这一点也是某类型的值能在严格意义上称为一等值的条件, 最后, 对于静态作用域的语言, 调用返回函数时的引用环境和创建它时的不同, 返回的函数要能够记住创建它时的引用环境, 特别是返回它的函数的局部变量, 不能像普通情况那样存放于函数的调用堆梭, 从而被删除. 总之语言必须支持闭包. javascript 这几个条件都满足, 下面来看几个例子:

判断数据类型

javascript 采用鸭子类型的标准进行类型检查和获得参数多态性. 不过在有些场景中, 仍需手工依据某个值的类型采取行动, 例如当该值可能是不同的简单数据类型或数组, 函数等类型时, 需要执行不同的算法. typeof 能获取各个值的类型名称, 为了使用方便, 可以写出判断一个值是否为某个类型的谓词函数, 如 isString 判断一个值是否为字符串. 有些类型的值有简单或特殊的判断方法:

export function isUndefined(val) {
	return val === undefined
}

export const isArray = Array.isArray.bind(Array)

export function isNull(val) {
	return val === null
}

// 不能用 instanceof 判断一个值是否为对象类型, 因为存在 Object.prototype, Object.create(null) 两种假阴性的情况
function isObject(val) {
	return val instanceof Object;
}
// 也不能用 typeof 判断一个值是否为对象类型, 因为存在 null 假阳性, 函数和宿主对象假阴性的情况
function isObject(val) {
	return (typeof val === 'object');
}
// 巧妙利用 Object 函数的行为, Object 作为普通函数使用时, 能够接收任意类型的参数
// 当参数为简单类型, 则返回它的包装对象
// 当参数为对象, 则返回对象本身
// 当参数为 undefined 或 null, 则返回一个空对象
export function isObject(val) {
	return val === Object(val)
}

其他大部分类型的值还是依靠 typeof 来判断, 我们可以编写一个通用的函数来返回这些谓词函数:

function isA(type) {
	return function(val) {
		return typeof val === type
	}
}

const isString = isA('string')
const isFunction isA('function')
const isNumber = isA('number')

日志

Log4J等日志模块都有一个共同点, 那就是日志级别. 记录日志时需标记级别, 模块又能以某种方式设置当前所用级别, 只有当前者不小于后者时, 日志才会被输出到所用载体. 采用这种方式, 既能在代码中记录不同级别的信息, 又能根据需要通过设置获取各种级别的日志. 依据惯例, 会为若干常用的日志级别创建单独的函数, 以便使用, 如 DEBUG, INFO, WARN, ERROR 等. 它们通常会在输出的日志前加注相应的符号, 以示区别, 下面用 js 简单实现这种日志模式:

// 日志级别
const LEVEL = {
	DEBUG: 1,
	INFO: 2,
	LOG: 3,
	WARN: 4,
	ERROR: 5,
}

// 当前所用日志级别
let currentLevel = LEVEL.LOG;
// 创建不同级别的日志函数
function createLogger(level, prefix) {
	return function(...args) {
		if(f.gte(level, currentLevel) && f.gt(args.length, 0)) {
			let firstArg = f.first(args);
			if(isString(firstArg)) {
				firstArg = `${prefix} ${firstArg}`;
				return f.log(firstArg, ...f.rest(args));
			} else {
				return f.log(prefix, ...args)
			}	
		}
	}
}
const warn = createLogger(LEVEL.WARN, 'WARN:')
const debug = createLogger(LEVEL.DEBUG, 'DEBUG:')
warn(1,2)

读取对象属性

下面来看一个实际编程中常常会遇到的处理数据的例子, 如何采用函数返回值带来帮助, 现在有一个数组存储的是一个列车的时刻表, 我们需要从其中提取经停站点的名称, 当然我们可以向 map 函数传递一个临时创建的函数, 它返回参数对象的 stop 属性值:

f.log(f.map(item => item.stop, schedule))

但是当我们需要提取另外一个属性, 或者对象的属性发生变化, 就必须每次重新写一个函数. 一个更加抽象的方案是, 编写一个读取属性的通用函数, 它的参数是要读取的属性名称, 返回的不是属性值, 而是一个函数, 这个函数的参数是要读取其属性值的对象, 返回的才是最终需要的属性值:

function getAttr(attr) {
	return function(obj) {
		return obj[attr]
	}
}

const getStop = getAttr('stop')
f.log(f.map(getStop, schedule))

一个函数根据参数值返回不同的函数，相当于函数的工厂, 我们可以从不同角度来认识这种编程模式的好处, 与手工逐个编写返回的那些函数相比, 使用函数返回值的代码更加简洁, 易于维护. 函数能作为返回值的好处是它极大地拓展了函数功能的可能性, 提高了函数应用的灵活性 .

高阶函数

一个函数, 如果接受其他函数作为参数或者返回值是函数, 就称为高阶函数(High-order function), 前面说到的函数都只具备一个特征, 这里的高阶函数专注于两者皆有的高阶函数.

组合谓词函数

假设我们要从列车时刻表中找出起点站和终点站. 根据站点的 arrival 和 departure 属性值是否为 null, 可以写出判断站点是否为起点站或终点站的谓词函数. 再将该函数传递给 filter 函数, 就能得到结果:

function isOriginOrTerminal(stop) {
	return stop.arrival === null || stop.departure === null;
}

f.log(f.filter(isOriginOrTerminal, schedule));

假如需求变成了找出经停站点(起点站和终点站之外的站点), 最简单的思路是写一个判断站点是否为经停站点的谓词函数, 也就是将 isOriginOrTerminal 函数的返回值改成其否定值. 另一种思路是写一个通用的高阶函数 complement, 它接收一个谓词函数作为参数, 返回一个新的谓词函数. 对于任何参数, 新的谓词函数总是得出原有谓词函数返回值的否定值, 或者称为补值(complement), 利用该高阶函数, 我们就不需要再编写判断站点是否为经停站点的谓词函数:

function complement(pred) {
	return function(...args) {
		return !pred(...args)
	}
}

同理, 我们还能写出高阶函数 both 和 either, 它们接受两个谓词函数作为参数, 返回一个新的谓词函数. 对于任何参数, 新的谓词函数总是分别得到原有两个函数返回值的与值和或值:

export function both(pred1, pred2) {
	return function(...args) {
		return pred1(...args) && pred2(...args)
	}
}

export function either(pred1, pred2) {
	return function(...args) {
		return pred1(...args) || pred2(...args)
	}
}

有了这类函数, 我们可以把isOriginOrTerminal拆分成含义和逻辑更简单的两个函数, isOrigin 用来判断某个站点是否是起点, isTerminal 用来判断某个站点是否为终点. 一系列更复杂的谓词函数都能以这些原子函数为原料, 利用上面的高阶函数组合出来:

function isOrigin(stop) {
	return stop.arrival === null
}

function isTerminal(stop) {
	return stop.departure === null
}

f.log(f.filter(f.either(isOrigin, isTerminal), schedule))

采用上述关于逻辑的高阶函数, 我们能立即计算出所需的谓词函数, 同时也会促使我们编写尽可能简单的谓词函数, 使得代码层次清楚, 含义一目了然.

改变函数参数数目

javascript 数组对象的迭代方法有一个函数参数, 在调用该函数时传递的参数, 除了包括必不可少的迭代的当前元素, 还有当前索引和数组本身, 传递给迭代方法的函数假如定义有超过一个形式参数, 而期望的参数值又不是迭代的当前索引和数组, 就会产生意想不到的错误:

const vals = ['1', '2']
f.log(f.map(parseInt, vals))

这里导致错误的原因在于, parseInt 函数比它看上去要复杂, 它的功能不仅仅是将一个字符串转换成整数, 而是转换成各种进制的整数. 它有两个形式参数, 第一个是待转换的字符串, 第二个是整数所用的进制, 需要为2到36的整数. 当第二个参数未被提供或为0时, 函数根据字符串的形式来选用进制, 以 '0x' 开始的字符串选用十六进制, 以 '0' 开始的字符串选用8进制或十进制, 其他情况则用十进制. 字符串无法转换时, 返回 NaN. 第二个参数为无效的1时, 也返回NaN. 因此调用 parseInt 时最好提供两个参数, 如能确保默认的进制正确, 也可省略第二个参数. 这里的索引被错误的当成了进制, 导致了错误的结果. 解决方法是创建 parseInt 函数的简化版本, 它只接收一个参数, 使用默认的进制将其转换成整数, 为此我们可以定义一个通用的高阶函数, 它将作为参数接收的任意多元函数包装成一元函数:

export function unary(fn) {
	return function(arg) {
		return fn(arg)
	}
}

f.log(f.map(f.unary(parseInt), vals))

类似这样改变函数参数数目(或称为元数 Arity) 的模式还有其他用途. 比如我们要将一个嵌套数组压扁:

const nested = [[1,2], [3,4,5], [6]]
f.log(nested.reduce(Array.prototype.concat(bind([]), []))

这里没有得到期望的结果, 原因与上面类似, Array.prototype.concat方法能接收任意多个数组, 将它们合并起来, 数组的 reduce 方法除了将其元素两两传递给 concat 函数之外, 还会传递当前索引和数组本身, 这就解释了最后的结果, 我们可以将 concat 包装成一个二元函数, 这要利用到另一个通用的高阶函数binary:

function binary(fn) {
	return function(a, b) {
		return fn(a, b)
	}
}

可以想到, 还会有需要三元或者更多元函数的场景, 因此可以定义一个更高阶的函数, 它接收一个元数作为参数, 返回一个将任何函数包装成指定元数函数的函数:

function nAry(arity) {
	return function(fn) {
		return function(...args) {
			let accepted = f.take(arity, args);
			return fn(...accepted);
		}
	}
}

像 unary, binary 这样的高阶函数, 接收一个函数作为参数, 返回一个调整和改变了该函数行为的新函数, 可以归纳为函数式编程中的装饰器模式, 因为它可以在不修改原函数代码的情况下, 调整或增强该函数的功能.

检查函数的参数类型

我们可以定义一个高阶函数, 它接收待检查的函数作为参数, 返回的装饰过的函数则具备了检查参数类型的功能：

export function checkTypes(fname, fn, ...types) {
	return function(...args) {
		if(!Array.isArray(types[0])) {
			types = [types];
		}
		let received = args.map(typeof)
		if(!types.some(expected => arrayEqual(expected, received))) {
			let msg = `Unexpected argument type for ${fname}: ${received.join(', ')}`
			error(msg, TypeError)
		}
		return fn(...args)
	}
}

记忆化

缓存是提高程序性能的重要技术, 对于输入输出, 高耗资源的计算等需要花费较长时间的功能, 将结果保存在能快速访问的载体里, 以后遇上同样的调用, 就直接读取上次保存的结果, 从而大大节省时间, 简单来说就是以空间换时间, 在函数式编程中, 对单个函数使用缓存的技术, 称为记忆化. 一般选取的缓存载体是映射, 这在 javascript 里有两种选择, 通用的对象和专用的映射. 映射更适合充当缓存, 我们用一组函数来包装映射类型的方法:

// 将某个对象的方法转换为函数
function invoker(name) {
	return function(...args) {
		const obj = args[args.length - 1]
		return obj[name](...args.slice(0, args.length - 1))
	}
}

// Map methods
export const has = f.invoker('has')
export const get = f.invoker('get')
export const set = f.invoker('set')
export const mapKeys = f.invoker('keys')

// 读取嵌套的映射中对应于一组键的值. 参数 keys 可能为单个键或多个键组成的数据
export function mapGet(keys, map) {
	if (!Array.isArray(keys)) {
		return mapGet([keys], map)
	}
	for (let key of keys) {
		map = get(key, map)
	}
	return map;
}

// 检查嵌套的映射中是否有对应于一组键的值
export function mapHas(keys, map) {
	if(!Array.isArray(keys)) {
		return mapHas([keys], map)
	}

	if(f.isZeroLength(keys)) {
		return true
	}

	const key = f.first(keys);
	if(has(key, map)) {
		map = get(key, map);
		return mapHas(f.rest(keys), map)
	} else {
		return false
	}
}

// 设置映射对应于一组键的值
export function mapSet(keys, value, map) {
	if(!Array.isArray(keys) {
		return mapSet([keys], value, map)
	}
	const key = f.first(keys)
	if(keys.length === 1) {
		set(key, value, map)
		return
	}
	if(!has(key, map) || !(get(key, map) instanceof Map)) {
		set(key, new Map(), map);
	}
	mapSet(f.rest(keys), value, get(key, map))
}

接下来我们定义 memoize 函数, 它可以将任何函数变成一个记忆化的版本, 奥妙在于, 每当调用它返回的函数时, 程序会以参数为键, 检查位于该函数闭包中的一个作为缓存的映射:

export function memoize(fn) {
	const cache = new Map();
	return function(...args) {
		let val
		if(!mapHas(args, cache) {
			val = fn(...args)
			mapSet(args, val, cache)
		}
		val = mapGet(args, cache)
		return val
	}
}

接下来我们通过一个函数来测试记忆化函数:

// 计量一个函数运行所用的时间, Date.now() 只能精确到毫秒
// 采用 console.time 能获得更高的精度
export function tookTime(fn, ...args) {
	let fname = fn.name ? fn.name : 'anonymouse'
	let label = `${fname}(${args.join(',')})`
	console.time(label)
	log(fn(...args))
	console.timeEnd(label)
}

function sum(x) {
    let ret = 0
    for(let i = 1; i < x; i++) {
        ret += i
    }
    return ret
}

const memSum = f.memoize(sum)
f.tookTime(sum, 1000001)
f.tookTime(memSum, 1000001)
f.tookTime(memSum, 1000001)

一般来说, 记忆化的函数首次运行时的性能与原函数差不多, 因为要读写缓存, 用时可能会稍长, 但之后以同样参数运行时耗时都会稳定在一个很小的数字. 上面的结果在不同环境下运行会略有差别, 这里之所以第二次运行比第一次时间还短, 是得益于 js 引擎再次运行某一函数时所做的性能优化