functional.js 介绍及源码分析

引用

本文对刚刚在网络上现身的 JavaScript 函数式编程库 functional.js 进行详尽的解读（地址已更正，感谢 hax）。

functional.js 是模仿 Haskell 语言标准库 Prelude 制作的函数式编程库，主要实现了：

• 扩展的克里化函数
• 运算符函数化
• 紧缩的匿名函数语法
• 无须指定参数的匿名函数语法
• 函数向导语法
• 基本的通用列表操作
• 部分扩展基于对象化

其中，扩展语法由字符串表示。未能实现的特性有：

• 尾递归优化
• 模式匹配（包括参数匹配、列表匹配、情况分析）
• 惰性运算（包括无穷列表）
• 列表领悟
• 扩展绑定、同时绑定
• 其它列表操作（以及对于列表操作的基于对象化）

下面我们一边分析源代码，一边讲解库的用法。

一、库安装和概览
functional.js 库的所有用户级操作分为3个部分：

1. 全局操作，绑定在全局对象 Functional 上，主要是高阶函数操作和列表操作，所谓库安装即把这些内容可选的、安全地复制到全局环境
2. 函数扩展，实现特殊高阶函数特性的工具（特供内部）
3. 语法扩展，绑定在 String.prototype 上，负责将字符串表示的 lambda 语法翻译为相应的高阶函数（特供内部）

下面是安装函数 Functional.install 的源代码（中文注释为笔者所加，下同）：

Functional.install = function(except) { // except 参数是一个对象，不加载这些操作 
    var source = Functional,
        target = window; // 复制操作到全局环境 window，仅限于浏览器环境
    for (var name in source)
        name == 'install' // 当然，不能把 install 复制到 source
        || name.charAt(0) == '_' // 命名开头为 _，私有属性
        || except && name in except
        || {}[name] // work around Prototype
        || (target[name] = source[name]);
}

一般只要执行 Functional.install() 一句即可。

二、高阶函数操作
1. Functional.compose ([Function]) // 匿名的参数类型指的是 arguments 的类型，下同
　　接受一列参数个数被认为相等的（允许 Currying 算子）函数为参数，返回一个函数，它接受一定的参数，能够对它们累积倒序 apply 那列函数。
　　示例：compose('1+', '2*')(2) => 5
　　
2. Functional.sequence ([Function])
　　累积 apply 的顺序为参数顺序，为 compose 的反序。
　　示例：sequence('1+', '2*')(2) => 6

以上两个操作亦可见于 Function.prototype，用法：'1+'.lambda().sequence('2*')(2) ==> 6

3. Function.prototype.flip ()
　　返回一个函数，是原函数对象 this 参数接受顺序颠倒后的版本，不应属于函数扩展类。
　　示例：flip('a/b')(1, 2) => 2
　　
4. Function.prototype.saturate ([]) {
　　返回一个函数，是原函数对象 this 忽略自己接受的参数，仅接受指定参数的版本。
　　形式：f.saturate(args...)(args2...) == f(args...)
　　
5. Function.prototype.aritize (n::Number) // 有名的参数类型由 :: 指定，下同
　　返回一个函数，是原函数对象 this 忽略自己接受的参数列表中下标为 n 的参数的版本。
　　
6. Function.S (f, g::Function)
　　以单个大写字母命名的是函数的原子操作，应被收入 Functional 对象，这个很奇怪。
　　形式：S(f, g)(args...) == f(g(args...), args...)
　　
三、通用列表操作
1. 绑定在 Functional 对象上的部分完全照抄 Haskell Prelude 以及 Clean 的命名，它们是：

1. map(f, [x1, x2...]) = [f(x, 0), f(x2, 1), ...]
2. foldl, reduce(f, init, [x0, x1, x2]) == f(f(f(init, x0), x1), x2)
3. filer, select('%2', [1,2,3,4]) -> [1, 3]
4. foldr(f, init, [x0, x1, x2]) == fn(x0, f(x1, f(x2, init)))
5. some(f, [x1, x2, x3, ...]) == f(x1) || f(x2) || f(x3)...
6. every(f, [x1, x2, x3, ...]) == f(x1) && f(x2) && f(x3)...

以上操作的介绍网上到处都是，不再赘述；但有一点不同，即它们除了接受正常参数之外，还在最后接受一个可选参数 object::Object，它被用于指定操作执行的对象/环境。
另外，这些操作全部基于命令式风格实现，对于没有尾递归优化的 JavaScript 来说，效率有保障。

四、群体谓词操作
1. Functional.and ([Function])
　　接受一列函数为参数，返回一个函数，它接受一个参数，对该参数 apply 那列函数，如结果全为 true，返回 true；否则返回 false。
　　形式：and(f1, f2...)(args...) == f1(args...) && f2(args...)...
　　示例：and('>1', '>2')(2) => false
　　
2. Functional.or ([Function])
　　接受一列函数为参数，返回一个函数，它接受一个参数，对该参数 apply 那列函数，如结果全为 false，返回 false；否则返回 true。
　　形式：or(f1, f2...)(args...) == f1(args...) || f2(args...)...
　　示例：or('>1', '>2')(2) => true
　　
3. Functional.not = function(fn::Function)
　　返回一个函数，是参数返回的布尔值的函数（谓词，下同） fn 取否的版本。
　　形式：f.not()(args...) == !f(args...)
　　
4. Functional.equal ([Function])
　　接受一列函数为参数，返回一个函数，它接受一个参数，对该参数 apply 那列函数，如结果全部 == ，返回 true；否则返回 false。
　　形式：equal(f1, f2...)(args...) == f1(args...) == f2(args...)...
　　示例：equal()() => true // 特殊情况

五、函数扩展
　　这一章仅仅是介绍内部实现。
1. Function.prototype.bind (object::Object,[])
　　返回一个函数，作为 this 函数对象的副本，使其将在 object 环境下执行，并额外携带参数。
　　形式：f.bind(obj, args...)(args2...) == f.apply(obj, [args..., args2...])
　　
2. Function.prototype.curry ([])
这是实现克里化特性的关键函数，思想来自网络。

Function.prototype.curry = function(/*args...*/) {
    var fn = this;
    var args = [].slice.call(arguments, 0);
    return function() {
        return fn.apply(this, args.concat([].slice.call(arguments, 0)));
    };
}

　　返回那个传说中的可在参数不足时分步调用的函数——Currying 算子。
　　形式：f.curry(args1...)(args2...) == f(args1..., args2...)

其它的 curry 类函数有：

• rcurry，对从右边开始缺少参数的函数作克里化
• ncurry，不接受全部参数就不 apply 参数的版本
• rncurry，前者的反序版本
• uncurry，作者一再强调，这不是 curry 的反转版本。它会拆分出第一个已得参数，形式为：f.uncurry(a, b...) == f(a)(b...)

3. Function.prototype.partial ([])
　　在此函数定义之前，有定义 _ = Function._ = {} 。结合它们可以允许你像在 Haskell 中那样在参数列表中用 _ 忽略参数。但现在空谈是没用的，要结合第七章的语法扩展。
　　
4. Function.prototype.guard (guard:>Function, otherwise)
　　类似的，是一个允许在函数定义中使用向导功能的工具，尚缺少语法扩展支持。
　　形式：f.guard(g, h)(args...) == f(args...), when g(args...) is true
　　　　f.guard(g ,h)(args...) == h(args...), when g(args...) is false

六、工具函数
1. Functional.invoke (methodName::String, [])
　　示例：invoke('toString')(123) => "123"
　　
2. Functional.pluck (name::String)
　　示例：pluck('length')("abc") => 3
　　
3. Functional.until (pred:>Function, fn:>Function) // 用 :> 表示将参数强制转换类型

Functional.until = function(pred, fn) {
　　// 使用时参数会被强制转为 Functional 的函数，参数可为字符串
    fn = Function.toFunction(fn); 
    pred = Function.toFunction(pred); 
　　// 返回一个接受一个参数的函数，
    return function(value) {
　　　　// 它不断对此参数 apply 函数 pred，
        while (!pred.call(null, value))
　　　　　　// 并用 fn(value) 的值更新 value，
            value = fn.call(null, value);
        return value; // 直到测试结果为 true。
    }
}

　　类似 Haskell 的 until，是一种函数式的循环，用命令式风格实现。
　　
4. Functional.zip ([])
　　特别注意，此 zip 并非 Haskell 中的 zip，它接受可变参数列表而不是列表的列表。
　　形式：zip(a, b...) == [[a0, b0], [a1, b1], ...]

以上的章节中绑定在 Functional 上函数都可作为 Function 的对象方法直接使用，我们看这一行：

Functional.__initalFunctionState = 
Functional._startRecordingMethodChanges(Function.prototype);

前文对它们作出了定义，这里忽略。用法：name(arg, args...) == arg.name(args...)。

七、语法扩展
1. String.prototype.lambda ()
　　把字符串表示的字符串翻译为函数扩展可接受的函数，进一步转为 JavaScript 函数。

String.prototype.lambda = function() {
    var params = []; // 存储字符串形式的参数的列表
    var expr = this;
　　// ECMAsplit 是作者为兼容 IE6.0 所写的 split 版本
    var sections = expr.ECMAsplit(/\s*->\s*/m); // 使字符串被 '->' 分割
　　/* 注意，分割的结果支持超过任意个 '->'，下面会发现，
　　　　-> 9 或者
　　　　x -> y -> x+y 这样的代码也会被正确理解。
　　*/
    if (sections.length > 1) {
　　　　// 这就是所谓的“正确理解”了
        while (sections.length) {
            expr = sections.pop();
　　　　　　// 然后把参数打碎，再重组为 JS 可识别的参数语法
　　　　　　/* 也就是说，x y -> x*y+2 和
　　　　　　　　x,y -> x*y+2 都可被接受。
　　　　　　*/
            params = sections.pop().split(/\s*,\s*|\s+/m);
　　　　　　// 装配成代码，顺便支持尾递归语法
            sections.length && sections.push('(function('+params+'){return ('+expr+')})'); 
        }
    } else if (expr.match(/\b_\b/)) {
        params = '_'; // 忽略参数的前奏，下文判断
    } else {
　　　　// 这里处理运算符表达式参数缺失的情况，相当于运算符函数化
　　　　// 分为前缺失和后缺失两种情况，
        var leftSection = expr.match(/^\s*(?:[+*\/%&|\^\.=<>]|!=)/m);
        var rightSection = expr.match(/[+\-*\/%&|\^\.=<>!]\s*$/m);
　　　　/* 注意，前缺失类似 *2，后缺失类似 2*，复杂表达式同样支持
　　　　　　此外，前后都缺失也可以，比如 * 甚至是 *3*
　　　　*/
        if (leftSection || rightSection) {
　　　　　　// 翻译缺失代码的技术：用 $1、$2 代换参数
            if (leftSection) {
                params.push('$1');
                expr = '$1' + expr;
            }
            if (rightSection) {
                params.push('$2');
                expr = expr + '$2';
            }
        } else {
　　　　　　// 这个地方就有点意思了；它使得函数支持参数指定缺失
　　　　　　/* 比如 x*y 就已经是一个函数了，相当于 x y->x*y
　　　　　　　　作者还特别防止了一个 bug，即对象属性访问语法中，
　　　　　　　　属性部分不被认为是未指定的参数。例如
　　　　　　　　obj.pro + 4 这个函数，只有 obj 一个参数
　　　　　　　　而且，this 和 arguments 不会被认为是未知数。
　　　　　　*/
            var vars = this.replace(/(?:\b[A-Z]|\.[a-zA-Z_$])[a-zA-Z_$\d]*|[a-zA-Z_$][a-zA-Z_$\d]*:|this|arguments|'(?:[^'\\]|\\.)*'|"(?:[^"\\]|\\.)*"/g, '')
			.match(/([a-z_$][a-z_$\d]*)/gi) || []; 
            for (var i = 0, v; v = vars[i++]; )
                params.indexOf(v) >= 0 || params.push(v);
        }
    }
    return new Function(params, 'return (' + expr + ')'); // 把代码装配成函数对象
}

八、过滤器生成器
　　仅供特别好学的同志们参考。
1. Function.prototype.prefilterObject (filter::Function)
　　形式：fn.prefilterObject(filter).apply(object, args...) == fn.apply(filter(object), args...)
　　
2. Function.prototype.prefilterAt (index::Number, filter::Function)
　　形式：fn.prefilterAt(i, filter)(a1, a2, ..., a_{n}) == fn(a1, a2, ..., filter(a_{i}), ..., a_{n})
　　
3. Function.prototype.prefilterSlice (filter::Function, start, end::Number)
　　形式：fn.prefilterSlice(i0, i1, filter)(a1, a2, ..., a_{n}) == fn(a1, a2, ..., filter(args_{i0}, ..., args_{i1}), ..., a_{n})

九、其它用户级函数
1. Functional.id = Functional.I = function(x) {return x};

2. Functional.constfn = Functional.K = function(x) {return function() {return x}};

3. .toFunction ()
　　在 String.prototype，Function.prototype，Function（需要参数 fn::Function） 上都有绑定，把对象转换为一个合适的 Functional 函数。但你不需要把代码写这样，map('*2'.toFunction(),alist)，因为全局用户级函数都会对应为函数的参数自动执行 toFunction()，只要 map('*2',alist) 就行了。另外，String.prototype 上还有 JavaScript-Like 的 call、apply 方法。

十、结语
　　functional.js 很强，[url=http://osteele.com/archives/2007/07/functional-javascript ]很有用[/url]，很牛X；但同时也很年轻（7.20 发布），很多可以实现的功能还不完善，不说列表领悟什么的吧，至少应该把 Haskell Prelude 库在通用列表操作方面的函数的移植工作完成。我们期待 Oliver Steele 的表现。

评论

9 楼 achun 2008-07-09  

是不是写错了注释

引用

name == 'install' // 当然，不能把 install 复制到 source

 
应该是

引用

name == 'install' // 当然，不能把 install 复制到 target

8 楼 afcn0 2007-10-24  

看了下Oliver Steele写的js，也是大师级水准呀，高人真多

7 楼 kaki 2007-10-24  

下再看看。

6 楼 i_love_sc 2007-07-31  

看起来还是有点困难啊。

5 楼 cookoo 2007-07-30  

-_-||| 你又较真了，轻松点嘛

4 楼 Lich_Ray 2007-07-29  

cookoo 写道

又一桩haskell被消化掉的惨案，哈哈

Haskell 被消化掉；你觉得这可能吗？说反了吧，应该是“又一桩 haskell 施舍特性的案例”。Haskell 能做到的，不是语义等价的语言至多望其项背，分点残羹冷炙。然后 Scheme 就看着这些家伙吃 Haskell 的牙垢，在一旁冷笑~~ Lisp 前辈说的好：姜还是老的辣！

3 楼 hax 2007-07-27  

地址应为http://osteele.com/sources/javascript/functional/

2 楼 cookoo 2007-07-27  

又一桩haskell被消化掉的惨案，哈哈

ruby也有个prelude实现，gem包就叫prelude

1 楼 codemonkey 2007-07-26  

顺便八卦一下，Oliver Steele是Marvin Minsky的女婿，也是OpenLaszlo的主程。