luochen1990 edited this page Nov 30, 2014 · 11 revisions

CoffeeMate

(a FP lib via & for CoffeeScript)

通过定义工具函数实现语法增强

macro demo

log宏

输出log是一个很常用的调试手段,我们写过太多这样的代码

console.log "x + y:", x + y

当然作为一个CoffeeScript用户我们更倾向于写成这样

console.log "x + y: #{x + y}"

但是不管哪种写法都改变不了我们需要写两遍x + y的事实,不仅没有效率,而且当我想改变x + y的时候,我还得同时改这两处,多么痛苦的事情!

所以我hack了这样一个叫做log的debug工具,它不是什么新语法,仅仅是一个普通的JS函数,用它你可以直接写成这样

log -> x + y

它就能输出一个类似这样的东西

## x + y ==> 3

这是一件多么幸福的事情

assert宏

类似的需要打印代码的情景还有assert(断言),不幸JS也没有这个语法,所幸的是我也用类似的办法hack实现了

assert -> 1 < 0

打印

ASSERTION FAILED: 1 < 0

dict函数——字典解析

CoffeeMate做的其它语法增强还有dict函数和cart函数

dict函数用来弥补CoffeeScript缺失的字典解析功能,当然你不能怪CoffeeScript,毕竟JS连真正的字典也是直到最近的新标准才有 :)

dict([i, i * i] for i in [1..3])

得到的是字典

{"1": 1, "2": 4, "3": 9}

cart函数——嵌套列表解析

cart函数取名自笛卡尔积(cartesian product),用来弥补CoffeeScript不支持的嵌套列表解析

例如如果你想得到[1..9]的乘法表,你得这样写

r = do ->
	ls = []
	for i in [1..9]
		for j in [1..9]
			ls.push (i * j)
	return ls

而不能像类似python一样这样写

r = ((i * j) for i in [1..9] for j in [1..9])

因为这会被CoffeeScript理解为

r = (((i * j) for i in [1..9]) for j in [1..9])

那么用CoffeeMate提供的cart函数你就可以这样写

r = ((i * j) for [i, j] in list cart([1..9], [1..9]))

这里多出了一个list函数,这是因为cart函数是支持延迟求值的,要利用它延迟求值的特性你可以这样写

r = list map(([i, j]) -> i * j) cart([1...9], [1...9])

这样的话就不需要在遍历前构造出一个临时的笛卡尔积的列表,从而节省了内存分配的时间开销

一个Javascript延迟求值函数库的设计

延迟求值是函数式编程中一个重要的概念,通过延迟求值技术,我们很容易用有限的空间表达一个无限可枚举的集合。然而Javascript并没有任何语法支持延迟求值,但我不觉得这代表Javascript不支持延迟求值,我甚至觉得ES6新加入的类似python的yield语句某种意义上有些画蛇添足。为了说明这一点,我试图在不引入任何新语法的情况下,给出一个Javascript的延迟求值方案。

我们先一起来看一个简单的伪随机数生成器的代码

hash = (x) ->
	x = Math.sin(x) * 1e4
	x - Math.floor(x)

random_gen = (seed) ->
	cnt = hash(seed)
	-> hash(++cnt)

我们可以这样使用它

random = random_gen(0)
console.log random()
console.log random()
console.log random()

你会发现,我们调用了3次random函数,它返回了3个不同的值。这是如何做到的呢?聪明的你肯定早就发现了,不就是random函数引用了闭包内部的cnt变量么。于是我们发现,通过返回一个引用了闭包内状态的函数,我们得到了一个“有状态的函数”,一个这样的函数可以在每次被调用时返回不同的值。我必须承认我这样做引入了状态,不够“函数式”,但是我可以让你看看如果用“纯函数”(combinator)实现一个类似的伪随机数生成器,它会长什么样

hash = (x) ->
	x = Math.sin(x) * 1e4
	x - Math.floor(x)

random_gen = (seed) ->
	f = (cnt) ->
		-> [hash(cnt+1), f(cnt+1)]
	f(hash(seed))

然后你得这样调用它

next_random = random_gen(0)
[r, next_random] = next_random()
console.log r
[r, next_random] = next_random()
console.log r
[r, next_random] = next_random()
console.log r

很显然,它并不会变得更好,从易用的角度来看这是显而易见的,在前一种实现中,我们只管调用就好了,状态变化的过程被封装进了random_gen函数的实现中,从而自动完成了;而后一种实现中,我们需要手动维护其状态,以使得next_random每次指向一个新的函数。而从概念的美感上来讲,后一种实现同样没有避免“有状态的东西”,next_random还是不可避免的有了状态,虽然它的状态变化在外部而不是内部。当然你也可以说我们通常会用一些别的辅助函数(如take,foreach)来执行迭代过程,所以它是否方便直接调用影响不大。

事实上我们可以无限次地调用这个random函数从而得到一个无限长度的随机数序列,并且我们每次调用random_gen函数的时候,只要我们给的seed参数一样,我们就能得到一个全新的返回值函数(就是前面的random),我们不停地调用这些函数总能得到一个相同的随机数序列,这里的每个random函数就像是一个c++里的迭代器。

哇,这不就是一个无限长度的可枚举集合么! 我们就这么不经意间发现了一种实用的描述可枚举集合的办法:对一个有状态的函数,列出对它的每次调用所返回的值,就构成了一个可枚举集合。

于是我们可以这样描述自然数集合

nature_number = (first = 0) -> i = first-1; (-> ++i)

然后我们试试看

f = nature_number()
console.log f()
console.log f()
console.log f()

我感觉到,这真是最自然的方式了,不需要引入额外的语法,任何编程语言,只要支持第一类函数和闭包,就可以用这种方式描述任何的可枚举集合。

显然,一个Javascript列表,如[1, 2, 3],也是一个可枚举集合,只不过它是有限的,我们可以写个函数来将它转变成我们的延迟求值形式(得到的是一个迭代器),为了标记迭代过程的结束,我们引入iter_end符号,它不与任何其它值相等。

iter_end = new Object

iterator = (ls) ->
	i = -1
	->
		i += 1
		if i < ls.length
			ls[i]
		else
			iter_end

为了让iterator函数使用起来就像一个强制类型转换函数,我们需要让不需要转换的东西直接通过,并且对无法转换的东西报错;另外,我们还需要考虑列表中存在iter_end值的情况,由于列表的结尾显然应该由列表的长度来决定,所以我们不能直接将iter_end返回,而应该将它替换成某个非特殊的值,所以我们允许用户传一个第二参数replaced_end来决定要将iter_end替换成什么,于是下面是新的iterator函数

iterator = (iterable, replaced_end) ->
	return iterable if typeof(iterable) is 'function'
	throw 'ERR IN iterator(): ONLY Array & Iterator IS ACCEPTABLE' if not iterable instanceof Array
	i = -1
	->
		i += 1
		if i < iterable.length
			if iterable[i] is iter_end
				if not replaced_end?
					throw 'ERR IN iterator(): iterator.end APPEARS IN LIST, PASS A SECOND ARG FOR REPLACEMENT'
				replaced_end
			else
				iterable[i]
		else
			iter_end

当然我们也会需要有一个函数可以将一个“有限可枚举集合的延迟求值形式”强制求值从而转换成一个“列表”,这个list函数用起来仍然像一个强制类型转换函数

list = (iterable) ->
	return iterable if typeof(iterable) isnt 'function'
	(x while (x = iterable()) isnt iter_end)

我们已经用random_gen,nature_number描述了伪随机数序列和自然数序列的延迟求值形式,并且现在我们可以用iterator函数将任意列表转变为延迟求值形式。用类似的方式,我们可以构造出任意的我们需要的可枚举集合,现在,我们需要一些工具来对这些可枚举集合作运算,这样我们可以以更快、更简单、更可读的方式构造出大量的可枚举集合。

比如我们可能需要在给出一个转换函数f的情况下,对集合a中的每个元素作f转换,形成一个新集合b,我们把这样一个运算叫做map,它用起来像这样

a = iterator [0...26]
f = (i) -> chr(ord('a') + i)
b = map(f) a
console.log list(b) # ['a', 'b', ... 'z']

我们还需要一个函数可以用来取一个可枚举集合的前n项,我叫它take

a = take(10) nature_number()
console.log list a # [0, 1, 2, ... 9]

当然我们可以根据一个判断函数去挑选一个集合中的某些元素构成一个新的集合,这个过程叫filter

f = (x) -> x % 3 == 0 or x % 5 == 0
a = filter(f) take(10) nature_number()
console.log list a #[0, 3, 5, 6, 9, 10]

我们可能还需要构造一个“拉链函数”,我们叫它zip,它传入一系列可枚举集合,返回一个新的可枚举集合,新集合的每一个元素是参数集合中相应位置上的元素构成的元组,它用起来像这样

a = iterator [0...26]
b = map((i) -> chr(ord('a') + i)) a
console.log list zip(a, b) # [[0, 'a'], [1, 'b'], ... [25, 'z']]

我们当然还想要构造一系列有限集合的笛卡尔积(cartesian product),这个被我叫做cart的函数可以这样用

a = [1, 2, 3]
b = ['a', 'b']
console.log list cart(a, b) # [[1, 'a'], [1, 'b'], [2, 'a'], [2, 'b'], [3, 'a'], [3, 'b']]

CoffeeScript通过自己定义的语法实现了列表解析,而事实上,通过我们的各种对可枚举集合的运算函数来以字面值而非过程的形式表达一个可枚举集合真的是一件很容易的事情,比如对于

b = (f(x) for x in a when g(x))

我们可以写成

b = map(f) filter(g) a

而对于需要用到index的情形

b = (f([i, x]) for x in a when g([i, x]))

我们同样可以写成

b = map(f) filter(g) enumerate(a)

为了迭代一个可枚举集合,我实现了一个foreach函数,它可以这样用

foreach take(10)(nature_number()), (x) ->
	console.log x
	return foreach.break if x > 5

你也可以直接用它来构造一个返回值

a = foreach take(10)(nature_number()), ((x, r) -> r.push(x) if x % 3 == 0), []
console.log a

你可以这样子通过foreach来实现求和函数sum

sum = (iter) ->
	foreach(iter, ((x, r) -> r.first += x), [0]).first
console.log sum take(100) nature_number() # 4950

如果你需要中途break出循环,你可以返回一个foreach.break来告诉foreach函数

[r] = foreach nature_number(), (x, r) ->
	if x >= 100 then foreach.break else r.first += x
, [0]
console.log r

当然这个写法太“过程式”了,其实你可以用takeWhile函数来做这件事

sum = (iter) ->
	foreach(iter, ((x, r) -> r.first += x), [0]).first
console.log sum takeWhile((x) -> x < 100) nature_number()

有了这些工具,我们可以试试写一个质数生成器

prime_number = ->
	filter((x) -> all((p) -> x % p != 0) takeWhile((p) -> p * p <= x) range(2, Infinity)) range(2, Infinity)
当然筛质数有更快的算法(线性筛法),但这个算法是根据质数定义而来的,并且它的空间复杂度是O(1)的,所以只要你有足够的耐心,它可以生成无限的质数,而线性筛法能得到的质数受限于计算机的内存大小

如果你熟悉质数的定义,那么这段代码简直太直白了,如果你试着给这段代码写一些注释,那它差不多是这样的

# filter the numbers from 2 to Infinity by (if for all p from 2 to until p * p > x, "this number" % p != 0)

你会觉得,这行注释真是太多余了!它既没有让事情变得更好理解,也没有描述得更简洁

你可以这样读这段代码:filter(...) range(2, Infinity) 就是说,用一个过滤器过滤从2到无穷的序列,就得到了我们要的东西(质数表),那么...中的过滤条件是什么呢,(x) -> all((p) -> x % p != 0) takeWhile((p) -> p * p <= x) range(2, Infinity) 是这样一个函数,对于输入x,遍历从2到p * p <= x的所有数,如果对每一个数p都满足(p) -> x % p != 0 (即x不整除p),那么返回true (即x是质数)

如果你把代码写成下面的样子,那么以上解释也是多余了 :)

prime_number = do ->
	is_prime = (x) ->
		all((p) -> x % p != 0) takeWhile((p) -> p * p <= x) range(2, Infinity)
	->
		filter(is_prime) range(2, Infinity)
Clone this wiki locally
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.