1. 原题
http://lisperator.net/blog/a-little-javascript-problem/
不能使用数组或对象，实现4个函数range，map，reverse，foreach，
完成以下功能，
var numbers = range(1, 10);
numbers = map(numbers, function (n) { return n * n });
numbers = reverse(numbers);
foreach(numbers, console.log);
/* output:
100
81
64
49
36
25
16
9
4
1
*/
2. 分析
首先看foreach，它的调用方式为CPS（continuation-passing style）。
因此，考虑range，map，reverse的实现可以是CPS方式。
（1）range
const range = const range = (min, max) => cont => {
for (let i = min; i <= max; i++) {
cont(i);
}
};
range会返回一个函数cont => {}，这个函数通过传入它的continuation来获取执行结果。
（2）map
const map = (r, fn) => cont => r(i => cont(fn(i)));
map比较简单，在调用cont之间调用以下fn就行了。
（3）foreach
const foreach = (r, cont) => r(cont);
foreach更简单，直接对函数传入cont进行调用。
（4）reverse
reverse比较麻烦，关键是我们怎样倒序调用cont，
考虑到函数调用栈是可以保存上下文的，
因此，我们可以利用函数调用，来实现倒序。
const reverse = r => cont => {
let f = () => 0;
r(i => f = (g => () => {
cont(i);
g();
})(f));
f();
};
对于r回调中的每个i，都会更新f，更新后的f中保存了上一个f的调用，
当前f被调用的时候，先调用cont(i)，然后在调用上一个f，
如此下去，最后一个f被调用时，先触发的是最后一个cont(i)。
3. 测试一下
const range = (min, max) => cont => {
for (let i = min; i <= max; i++) {
cont(i);
}
};
const map = (r, fn) => cont => r(i => cont(fn(i)));
const reverse = r => cont => {
let f = () => 0;
r(i => f = (g => () => {
cont(i);
g();
})(f));
f();
};
const foreach = (r, cont) => r(cont);
var numbers = range(1, 10);
numbers = map(numbers, function (n) { return n * n });
numbers = reverse(numbers);
foreach(numbers, console.log); // 100 81 64 49 36 25 16 9 4 1
4. reverse的其他方式
（1）foldr和foldl
对一个调用方式实现倒序，让我想起了用foldr实现foldl的技巧。
myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
where step x g a = g (f a x)
代码可参考《Real World Haskell》第4章，Folding from the right。
其中 foldr 和 foldl 的定义如下，
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr step zero (x:xs) = step x (foldr step zero xs)
foldr _ zero [] = zero
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl step zero (x:xs) = foldl step (step zero x) xs
foldl _ zero [] = zero
可以证明，使用foldr实现的foldl，与foldl的定义是等价的，
myFoldl f z (x:xs)
<=> (foldr step id (x:xs)) z
<=> (step x (foldr step id xs)) z
<=> (\a -> (foldr step id xs) (f a x)) z
<=> (foldr step id xs) (f z x)
<=> myFoldl f (f z x) xs
因此模仿它，reverse可以这样实现，
const reverse = r => cont => {
let f = () => 0;
r(i => (g => f = () => g(cont(i)))(f));
f();
};
（2）利用递归
这个实现取自这里，
function* range(start, end) { for (let i = start; i <= end; ++i) yield i }
function* map(iter, fn) { for (const x of iter) yield fn(x) }
function* reverse(iter) { for (const x of iter) yield* reverse(iter), yield x }
function foreach(iter, fn) { for (const x of iter) fn(x) }
var numbers = range(1, 10);
numbers = map(numbers, function (n) { return n * n; });
numbers = reverse(numbers);
foreach(numbers, console.log);
在reverse的实现中，先深度优先，递归的调用自己，
然后再在递归回溯的过程中，再 yield 出当前的x。
参考
A little JavaScript problem
easy-tips
Lucifier129 / A-little-JavaScript-problem.js
网友评论