Tail Call 优化递归函数
Tail Call Optimizing recursive function
这是一个深度扁平化数组的函数
const deepFlatten = (input) => {
let result = [];
input.forEach((val, index) => {
if (Array.isArray(val)) {
result.push(...deepFlatten(val));
} else {
result.push(val);
}
});
return result;
};
在一次讨论中，有人告诉我它的内存效率不高，因为它可能会导致堆栈溢出。
我在 http://2ality.com/2015/06/tail-call-optimization.html 中读到我可能会重写它以使其符合 TCO。
那会是什么样子，我如何衡量它的内存使用情况？
当递归调用在 forEach 内时，您无法对其进行优化，因为为了应用 TCO，编译器需要检查您是否没有保存上一次调用的 "state"。在 forEach 的情况下，您确实保存了当前位置的 "state"。
为了用 TCO 实现它，你可以重写 foreach 以用递归调用实现，它看起来像这样：
function deepFlattenTCO(input) {
const helper = (first, rest, result) => {
if (!Array.isArray(first)) {
result.push(first);
if (rest.length > 0) {
return helper(rest, [], result);
} else {
return result;
}
} else {
const [newFirst, ...newRest] = first.concat(rest);
return helper(newFirst, newRest, result);
}
};
return helper(input, [], []);
}
console.log(deepFlattenTCO([
[1], 2, [3], 4, [5, 6, [7]]
]));
您可以看到，在每个 return 中，唯一执行的操作是递归调用，因此，您不会在递归调用之间保存 "state"，因此编译器将应用优化.
递归函数优雅表达，尾递归优化甚至可以防止爆栈
然而，任何递归函数都可以转换为更丑陋的基于迭代器的解决方案，这可能只是在内存消耗和性能方面很漂亮，虽然不看。
参见：
也许这个不同方法的测试：https://jsperf.com/iterative-array-flatten/2
一般尾调用
我shared another functional approach to flattening arrays in JavaScript；我认为该答案显示了解决此特定问题的更好方法，但并非所有功能都可以很好地分解。这个答案将关注递归函数中的尾调用，以及一般的尾调用
一般来说，为了将循环调用移动到尾部位置，会创建一个辅助函数（下面的 aux），其中函数的参数包含完成该计算步骤所需的所有状态
const flattenDeep = arr =>
{
const aux = (acc, [x,...xs]) =>
x === undefined
? acc
: Array.isArray (x)
? aux (acc, x.concat (xs))
: aux (acc.concat (x), xs)
return aux ([], arr)
}
const data =
[0, [1, [2, 3, 4], 5, 6], [7, 8, [9]]]
console.log (flattenDeep (data))
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
js真的没有尾调用消除
但是，大多数 JavaScript 实现仍然不支持尾调用 - 如果您想在程序中使用递归而不用担心炸毁堆栈，则必须采用不同的方法 -
我目前的首选是 clojure 风格的 loop/recur 对，因为它为您提供堆栈安全性，同时让您的程序可以使用优美、纯粹的表达式编写
const recur = (...values) =>
({ type: recur, values })
const loop = f =>
{
let acc = f ()
while (acc && acc.type === recur)
acc = f (...acc.values)
return acc
}
const flattenDeep = arr =>
loop ((acc = [], [x,...xs] = arr) =>
x === undefined
? acc
: Array.isArray (x)
? recur (acc, x.concat (xs))
: recur (acc.concat (x), xs))
let data = []
for (let i = 2e4; i>0; i--)
data = [i, data]
// data is nested 20,000 levels deep
// data = [1, [2, [3, [4, ... [20000, []]]]]] ...
// stack-safe !
console.log (flattenDeep (data))
// [ 1, 2, 3, 4, ... 20000 ]
重要职位
为什么尾部位置如此重要？那么你有没有想过 return 关键字？这就是你的函数 out 的方式；在像 JavaScript 这样的严格评估的语言中，return <expr> 意味着 expr 中的所有内容都需要在我们发送结果之前进行计算。
如果expr包含一个子表达式，其函数调用不在尾部位置，这些调用将引入一个新的框架，计算一个中间值，然后return 它到尾部调用的调用帧 - 这就是为什么如果无法确定何时 安全 删除堆栈帧
堆栈可能溢出的原因
总之，编程很难讲，所以希望这个小草图能帮助识别一些常用函数的调用位置
const add = (x,y) =>
// + is in tail position
x + y
const sq = x =>
// * is in tail position
x * x
const sqrt = x =>
// Math.sqrt is in tail position
Math.sqrt (x)
const pythag = (a,b) =>
// sqrt is in tail position
// sq(a) and sq(b) must *return* to compute add
// add must *return* to compute sqrt
sqrt (add (sq (a), sq (b)))
// console.log displays the correct value becaust pythag *returns* it
console.log (pythag (3,4)) // 5
请稍等片刻——现在假设没有 return 值——因为函数无法将值发送回调用者，当然我们可以很容易地推断出在函数被评估后所有的帧都可以立即被丢弃
// instead of
const add = (x,y) =>
{ return x + y }
// no return value
const add = (x,y) =>
{ x + y }
// but then how do we get the computed result?
add (1,2) // => undefined
延续传球风格
进入Continuation Passing Style——通过为每个函数添加一个延续参数，就好像我们发明了我们自己的return机制
不要被下面的例子弄得不知所措——大多数人已经看到了以这些被误解的形式出现的延续传递样式，这些东西被称为 回调
// jQuery "callback"
$('a').click (event => console.log ('click event', event))
// node.js style "callback"
fs.readFile ('entries.txt', (err, text) =>
err
? console.error (err)
: console.log (text))
这就是您处理计算结果的方式 – 将其传递给延续
// add one parameter, k, to each function
// k makes *return* into a normal function
// note {}'s are used to suppress the implicit return value of JS arrow functions
const add = (x,y,k) =>
{ k (x + y) }
const sq = (x,k) =>
{ k (x * x) }
const sqrt = (x,k) =>
{ k (Math.sqrt (x)) }
const pythag = (a,b,k) =>
// sq(a) is computed, $a is the result
sq (a, $a => {
// sq(b) is computed, $b is the result
sq (b, $b => {
// add($a,$b) is computed, $sum is the result
add ($a, $b, $sum => {
// sqrt ($sum) is computed, conintuation k is passed thru
sqrt ($sum, k) }) }) })
// here the final continuation is to log the result
// no *return* value was used !
// no reason to keep frames in the stack !
pythag (3, 4, $c => { console.log ('pythag', $c) })
如何取出一个值?
这个 famous question: How do I return the response from an asynchronous call? 让数百万程序员感到困惑 – 只是，它真的与 "an asynchronous call" 无关，而与延续有关，而这些延续 return 有什么
// nothing can save us...
// unless pythag *returns*
var result = pythag (3,4, ...)
console.log (result) // undefined
没有 return 值，你 必须 使用延续将值移动到计算的下一步——这不是我的第一种方法试过这么说^^
但一切都在尾部位置！
我知道仅通过观察可能很难分辨，但每个函数在尾部位置都有 一个 函数调用——如果我们恢复 return 我们函数中的功能，调用 1 的值是调用 2 的值是调用 3 的值，等等——在这种情况下不需要为后续调用引入新的堆栈框架– 相反，调用 1 的帧可以重新用于调用 2，然后再次用于调用 3；我们仍然保持return值！
// restore *return* behaviour
const add = (x,y,k) =>
k (x + y)
const sq = (x,k) =>
k (x * x)
const sqrt = (x,k) =>
k (Math.sqrt (x))
const pythag = (a,b,k) =>
sq (a, $a =>
sq (b, $b =>
add ($a, $b, $sum =>
sqrt ($sum, k))))
// notice the continuation returns a value now: $c
// in an environment that optimises tail calls, this would only use 1 frame to compute pythag
const result =
pythag (3, 4, $c => { console.log ('pythag', $c); return $c })
// sadly, the environment you're running this in likely took almost a dozen
// but hey, it works !
console.log (result) // 5
一般尾调用；再次
将 "normal" 函数转换为连续传递样式函数可以是一个机械过程并自动完成 – 但是将所有内容放入尾部的 真正 点是什么位置？
好吧，如果我们知道第 1 帧的值是第 2 帧的值，也就是第 3 帧的值，依此类推，我们可以使用 while 循环手动折叠堆栈帧，其中计算结果在每次迭代期间就地更新——利用这种技术的函数称为 trampoline
当然，在编写递归函数时最常谈论蹦床，因为递归函数可以 "bounce"（产生另一个函数调用）很多次；甚至无限期——但这并不意味着我们不能在我们的 pythag 函数上演示一个只会产生几个 calls
的蹦床
const add = (x,y,k) =>
k (x + y)
const sq = (x,k) =>
k (x * x)
const sqrt = (x,k) =>
k (Math.sqrt (x))
// pythag now returns a "call"
// of course each of them are in tail position ^^
const pythag = (a,b,k) =>
call (sq, a, $a =>
call (sq, b, $b =>
call (add, $a, $b, $sum =>
call (sqrt, $sum, k))))
const call = (f, ...values) =>
({ type: call, f, values })
const trampoline = acc =>
{
// while the return value is a "call"
while (acc && acc.type === call)
// update the return value with the value of the next call
// this is equivalent to "collapsing" a stack frame
acc = acc.f (...acc.values)
// return the final value
return acc
}
// pythag now returns a type that must be passed to trampoline
// the call to trampoline actually runs the computation
const result =
trampoline (pythag (3, 4, $c => { console.log ('pythag', $c); return $c }))
// result still works
console.log (result) // 5
为什么要给我看这些？
因此，即使我们的环境不支持堆栈安全递归，只要我们将所有内容都放在尾部位置并使用我们的 call 助手，我们现在就可以将任何调用堆栈转换为循环
// doesn't matter if we have 4 calls, or 1 million ...
trampoline (call (... call (... call (...))))
在第一个代码示例中，我展示了使用 auxiliary 循环，但我也使用了一个非常聪明（尽管效率低下）的循环，它不需要深入重复数据结构——有时并不总是这样可能的;例如，有时您的递归函数可能会产生 2 或 3 个重复调用——那该怎么办？
下面我将向您展示 flatten 作为一个朴素的非尾递归过程——这里需要注意的重要一点是条件的一个分支导致 两个 对 flatten 的重复调用——这种树状重复过程起初似乎很难展平为迭代循环，但仔细、机械地转换为连续传递样式将表明这种技术几乎可以在任何 (如果不是全部）场景
[草稿]
// naive, stack-UNSAFE
const flatten = ([x,...xs]) =>
x === undefined
? []
: Array.isArray (x)
// two recurring calls
? flatten (x) .concat (flatten (xs))
// one recurring call
: [x] .concat (flatten (xs))
延续传球风格
// continuation passing style
const flattenk = ([x,...xs], k) =>
x === undefined
? k ([])
: Array.isArray (x)
? flattenk (x, $x =>
flattenk (xs, $xs =>
k ($x.concat ($xs))))
: flattenk (xs, $xs =>
k ([x].concat ($xs)))
用蹦床延续传球风格
const call = (f, ...values) =>
({ type: call, f, values })
const trampoline = acc =>
{
while (acc && acc.type === call)
acc = acc.f (...acc.values)
return acc
}
const flattenk = ([x,...xs], k) =>
x === undefined
? call (k, [])
: Array.isArray (x)
? call (flattenk, x, $x =>
call (flattenk, xs, $xs =>
call (k, $x.concat ($xs))))
: call (flattenk, xs, $xs =>
call (k, ([x].concat ($xs))))
const flatten = xs =>
trampoline (flattenk (xs, $xs => $xs))
let data = []
for (let i = 2e4; i>0; i--)
data = [i, data];
console.log (flatten (data))
wups，你不小心发现了 monad
[草稿]
// yours truly, the continuation monad
const cont = x =>
k => k (x)
// back to functions with return values
// notice we don't need the additional `k` parameter
// but this time wrap the return value in a continuation, `cont`
// ie, `cont` replaces *return*
const add = (x,y) =>
cont (x + y)
const sq = x =>
cont (x * x)
const sqrt = x =>
cont (Math.sqrt (x))
const pythag = (a,b) =>
// sq(a) is computed, $a is the result
sq (a) ($a =>
// sq(b) is computed, $b is the result
sq (b) ($b =>
// add($a,$b) is computed, $sum is the result
add ($a, $b) ($sum =>
// sqrt ($sum) is computed, a conintuation is returned
sqrt ($sum))))
// here the continuation just returns whatever it was given
const $c =
pythag (3, 4) ($c => $c)
console.log ($c)
// => 5
定界延续
[草稿]
const identity = x =>
x
const cont = x =>
k => k (x)
// reset
const reset = m =>
k => m (k)
// shift
const shift = f =>
k => f (x => k (x) (identity))
const concatMap = f => ([x,...xs]) =>
x === undefined
? [ ]
: f (x) .concat (concatMap (f) (xs))
// because shift returns a continuation, we can specialise it in meaningful ways
const amb = xs =>
shift (k => cont (concatMap (k) (xs)))
const pythag = (a,b) =>
Math.sqrt (Math.pow (a, 2) + Math.pow (b, 2))
const pythagTriples = numbers =>
reset (amb (numbers) ($x =>
amb (numbers) ($y =>
amb (numbers) ($z =>
// if x,y,z are a pythag triple
pythag ($x, $y) === $z
// then continue with the triple
? cont ([[ $x, $y, $z ]])
// else continue with nothing
: cont ([ ])))))
(identity)
console.log (pythagTriples ([ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]))
// [ [ 3, 4, 5 ], [ 4, 3, 5 ], [ 6, 8, 10 ], [ 8, 6, 10 ] ]
这是一个深度扁平化数组的函数
const deepFlatten = (input) => {
let result = [];
input.forEach((val, index) => {
if (Array.isArray(val)) {
result.push(...deepFlatten(val));
} else {
result.push(val);
}
});
return result;
};
在一次讨论中，有人告诉我它的内存效率不高，因为它可能会导致堆栈溢出。
我在 http://2ality.com/2015/06/tail-call-optimization.html 中读到我可能会重写它以使其符合 TCO。
那会是什么样子，我如何衡量它的内存使用情况？
当递归调用在 forEach 内时，您无法对其进行优化，因为为了应用 TCO，编译器需要检查您是否没有保存上一次调用的 "state"。在 forEach 的情况下，您确实保存了当前位置的 "state"。
为了用 TCO 实现它，你可以重写 foreach 以用递归调用实现，它看起来像这样：
function deepFlattenTCO(input) {
const helper = (first, rest, result) => {
if (!Array.isArray(first)) {
result.push(first);
if (rest.length > 0) {
return helper(rest, [], result);
} else {
return result;
}
} else {
const [newFirst, ...newRest] = first.concat(rest);
return helper(newFirst, newRest, result);
}
};
return helper(input, [], []);
}
console.log(deepFlattenTCO([
[1], 2, [3], 4, [5, 6, [7]]
]));
您可以看到，在每个 return 中，唯一执行的操作是递归调用，因此，您不会在递归调用之间保存 "state"，因此编译器将应用优化.
递归函数优雅表达，尾递归优化甚至可以防止爆栈
然而，任何递归函数都可以转换为更丑陋的基于迭代器的解决方案，这可能只是在内存消耗和性能方面很漂亮，虽然不看。
参见：
也许这个不同方法的测试：https://jsperf.com/iterative-array-flatten/2
一般尾调用
我shared another functional approach to flattening arrays in JavaScript；我认为该答案显示了解决此特定问题的更好方法，但并非所有功能都可以很好地分解。这个答案将关注递归函数中的尾调用，以及一般的尾调用
一般来说，为了将循环调用移动到尾部位置，会创建一个辅助函数（下面的 aux），其中函数的参数包含完成该计算步骤所需的所有状态
const flattenDeep = arr =>
{
const aux = (acc, [x,...xs]) =>
x === undefined
? acc
: Array.isArray (x)
? aux (acc, x.concat (xs))
: aux (acc.concat (x), xs)
return aux ([], arr)
}
const data =
[0, [1, [2, 3, 4], 5, 6], [7, 8, [9]]]
console.log (flattenDeep (data))
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
js真的没有尾调用消除
但是，大多数 JavaScript 实现仍然不支持尾调用 - 如果您想在程序中使用递归而不用担心炸毁堆栈，则必须采用不同的方法 -
我目前的首选是 clojure 风格的 loop/recur 对，因为它为您提供堆栈安全性，同时让您的程序可以使用优美、纯粹的表达式编写
const recur = (...values) =>
({ type: recur, values })
const loop = f =>
{
let acc = f ()
while (acc && acc.type === recur)
acc = f (...acc.values)
return acc
}
const flattenDeep = arr =>
loop ((acc = [], [x,...xs] = arr) =>
x === undefined
? acc
: Array.isArray (x)
? recur (acc, x.concat (xs))
: recur (acc.concat (x), xs))
let data = []
for (let i = 2e4; i>0; i--)
data = [i, data]
// data is nested 20,000 levels deep
// data = [1, [2, [3, [4, ... [20000, []]]]]] ...
// stack-safe !
console.log (flattenDeep (data))
// [ 1, 2, 3, 4, ... 20000 ]
重要职位
为什么尾部位置如此重要？那么你有没有想过 return 关键字？这就是你的函数 out 的方式；在像 JavaScript 这样的严格评估的语言中，return <expr> 意味着 expr 中的所有内容都需要在我们发送结果之前进行计算。
如果expr包含一个子表达式，其函数调用不在尾部位置，这些调用将引入一个新的框架，计算一个中间值，然后return 它到尾部调用的调用帧 - 这就是为什么如果无法确定何时 安全 删除堆栈帧
堆栈可能溢出的原因总之，编程很难讲，所以希望这个小草图能帮助识别一些常用函数的调用位置
const add = (x,y) =>
// + is in tail position
x + y
const sq = x =>
// * is in tail position
x * x
const sqrt = x =>
// Math.sqrt is in tail position
Math.sqrt (x)
const pythag = (a,b) =>
// sqrt is in tail position
// sq(a) and sq(b) must *return* to compute add
// add must *return* to compute sqrt
sqrt (add (sq (a), sq (b)))
// console.log displays the correct value becaust pythag *returns* it
console.log (pythag (3,4)) // 5
请稍等片刻——现在假设没有 return 值——因为函数无法将值发送回调用者，当然我们可以很容易地推断出在函数被评估后所有的帧都可以立即被丢弃
// instead of
const add = (x,y) =>
{ return x + y }
// no return value
const add = (x,y) =>
{ x + y }
// but then how do we get the computed result?
add (1,2) // => undefined
延续传球风格
进入Continuation Passing Style——通过为每个函数添加一个延续参数，就好像我们发明了我们自己的return机制
不要被下面的例子弄得不知所措——大多数人已经看到了以这些被误解的形式出现的延续传递样式，这些东西被称为 回调
// jQuery "callback"
$('a').click (event => console.log ('click event', event))
// node.js style "callback"
fs.readFile ('entries.txt', (err, text) =>
err
? console.error (err)
: console.log (text))
这就是您处理计算结果的方式 – 将其传递给延续
// add one parameter, k, to each function
// k makes *return* into a normal function
// note {}'s are used to suppress the implicit return value of JS arrow functions
const add = (x,y,k) =>
{ k (x + y) }
const sq = (x,k) =>
{ k (x * x) }
const sqrt = (x,k) =>
{ k (Math.sqrt (x)) }
const pythag = (a,b,k) =>
// sq(a) is computed, $a is the result
sq (a, $a => {
// sq(b) is computed, $b is the result
sq (b, $b => {
// add($a,$b) is computed, $sum is the result
add ($a, $b, $sum => {
// sqrt ($sum) is computed, conintuation k is passed thru
sqrt ($sum, k) }) }) })
// here the final continuation is to log the result
// no *return* value was used !
// no reason to keep frames in the stack !
pythag (3, 4, $c => { console.log ('pythag', $c) })
如何取出一个值?
这个 famous question: How do I return the response from an asynchronous call? 让数百万程序员感到困惑 – 只是，它真的与 "an asynchronous call" 无关，而与延续有关，而这些延续 return 有什么
// nothing can save us...
// unless pythag *returns*
var result = pythag (3,4, ...)
console.log (result) // undefined
没有 return 值，你 必须 使用延续将值移动到计算的下一步——这不是我的第一种方法试过这么说^^
但一切都在尾部位置！
我知道仅通过观察可能很难分辨，但每个函数在尾部位置都有 一个 函数调用——如果我们恢复 return 我们函数中的功能，调用 1 的值是调用 2 的值是调用 3 的值，等等——在这种情况下不需要为后续调用引入新的堆栈框架– 相反，调用 1 的帧可以重新用于调用 2，然后再次用于调用 3；我们仍然保持return值！
// restore *return* behaviour
const add = (x,y,k) =>
k (x + y)
const sq = (x,k) =>
k (x * x)
const sqrt = (x,k) =>
k (Math.sqrt (x))
const pythag = (a,b,k) =>
sq (a, $a =>
sq (b, $b =>
add ($a, $b, $sum =>
sqrt ($sum, k))))
// notice the continuation returns a value now: $c
// in an environment that optimises tail calls, this would only use 1 frame to compute pythag
const result =
pythag (3, 4, $c => { console.log ('pythag', $c); return $c })
// sadly, the environment you're running this in likely took almost a dozen
// but hey, it works !
console.log (result) // 5
一般尾调用；再次
将 "normal" 函数转换为连续传递样式函数可以是一个机械过程并自动完成 – 但是将所有内容放入尾部的 真正 点是什么位置？
好吧，如果我们知道第 1 帧的值是第 2 帧的值，也就是第 3 帧的值，依此类推，我们可以使用 while 循环手动折叠堆栈帧，其中计算结果在每次迭代期间就地更新——利用这种技术的函数称为 trampoline
当然，在编写递归函数时最常谈论蹦床，因为递归函数可以 "bounce"（产生另一个函数调用）很多次；甚至无限期——但这并不意味着我们不能在我们的 pythag 函数上演示一个只会产生几个 calls
const add = (x,y,k) =>
k (x + y)
const sq = (x,k) =>
k (x * x)
const sqrt = (x,k) =>
k (Math.sqrt (x))
// pythag now returns a "call"
// of course each of them are in tail position ^^
const pythag = (a,b,k) =>
call (sq, a, $a =>
call (sq, b, $b =>
call (add, $a, $b, $sum =>
call (sqrt, $sum, k))))
const call = (f, ...values) =>
({ type: call, f, values })
const trampoline = acc =>
{
// while the return value is a "call"
while (acc && acc.type === call)
// update the return value with the value of the next call
// this is equivalent to "collapsing" a stack frame
acc = acc.f (...acc.values)
// return the final value
return acc
}
// pythag now returns a type that must be passed to trampoline
// the call to trampoline actually runs the computation
const result =
trampoline (pythag (3, 4, $c => { console.log ('pythag', $c); return $c }))
// result still works
console.log (result) // 5
为什么要给我看这些？
因此，即使我们的环境不支持堆栈安全递归，只要我们将所有内容都放在尾部位置并使用我们的 call 助手，我们现在就可以将任何调用堆栈转换为循环
// doesn't matter if we have 4 calls, or 1 million ...
trampoline (call (... call (... call (...))))
在第一个代码示例中，我展示了使用 auxiliary 循环，但我也使用了一个非常聪明（尽管效率低下）的循环，它不需要深入重复数据结构——有时并不总是这样可能的;例如，有时您的递归函数可能会产生 2 或 3 个重复调用——那该怎么办？
下面我将向您展示 flatten 作为一个朴素的非尾递归过程——这里需要注意的重要一点是条件的一个分支导致 两个 对 flatten 的重复调用——这种树状重复过程起初似乎很难展平为迭代循环，但仔细、机械地转换为连续传递样式将表明这种技术几乎可以在任何 (如果不是全部）场景
[草稿]
// naive, stack-UNSAFE
const flatten = ([x,...xs]) =>
x === undefined
? []
: Array.isArray (x)
// two recurring calls
? flatten (x) .concat (flatten (xs))
// one recurring call
: [x] .concat (flatten (xs))
延续传球风格
// continuation passing style
const flattenk = ([x,...xs], k) =>
x === undefined
? k ([])
: Array.isArray (x)
? flattenk (x, $x =>
flattenk (xs, $xs =>
k ($x.concat ($xs))))
: flattenk (xs, $xs =>
k ([x].concat ($xs)))
用蹦床延续传球风格
const call = (f, ...values) =>
({ type: call, f, values })
const trampoline = acc =>
{
while (acc && acc.type === call)
acc = acc.f (...acc.values)
return acc
}
const flattenk = ([x,...xs], k) =>
x === undefined
? call (k, [])
: Array.isArray (x)
? call (flattenk, x, $x =>
call (flattenk, xs, $xs =>
call (k, $x.concat ($xs))))
: call (flattenk, xs, $xs =>
call (k, ([x].concat ($xs))))
const flatten = xs =>
trampoline (flattenk (xs, $xs => $xs))
let data = []
for (let i = 2e4; i>0; i--)
data = [i, data];
console.log (flatten (data))
wups，你不小心发现了 monad
[草稿]
// yours truly, the continuation monad
const cont = x =>
k => k (x)
// back to functions with return values
// notice we don't need the additional `k` parameter
// but this time wrap the return value in a continuation, `cont`
// ie, `cont` replaces *return*
const add = (x,y) =>
cont (x + y)
const sq = x =>
cont (x * x)
const sqrt = x =>
cont (Math.sqrt (x))
const pythag = (a,b) =>
// sq(a) is computed, $a is the result
sq (a) ($a =>
// sq(b) is computed, $b is the result
sq (b) ($b =>
// add($a,$b) is computed, $sum is the result
add ($a, $b) ($sum =>
// sqrt ($sum) is computed, a conintuation is returned
sqrt ($sum))))
// here the continuation just returns whatever it was given
const $c =
pythag (3, 4) ($c => $c)
console.log ($c)
// => 5
定界延续
[草稿]
const identity = x =>
x
const cont = x =>
k => k (x)
// reset
const reset = m =>
k => m (k)
// shift
const shift = f =>
k => f (x => k (x) (identity))
const concatMap = f => ([x,...xs]) =>
x === undefined
? [ ]
: f (x) .concat (concatMap (f) (xs))
// because shift returns a continuation, we can specialise it in meaningful ways
const amb = xs =>
shift (k => cont (concatMap (k) (xs)))
const pythag = (a,b) =>
Math.sqrt (Math.pow (a, 2) + Math.pow (b, 2))
const pythagTriples = numbers =>
reset (amb (numbers) ($x =>
amb (numbers) ($y =>
amb (numbers) ($z =>
// if x,y,z are a pythag triple
pythag ($x, $y) === $z
// then continue with the triple
? cont ([[ $x, $y, $z ]])
// else continue with nothing
: cont ([ ])))))
(identity)
console.log (pythagTriples ([ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]))
// [ [ 3, 4, 5 ], [ 4, 3, 5 ], [ 6, 8, 10 ], [ 8, 6, 10 ] ]