这是一个深度扁平化数组的函数
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-ed。
它看起来如何，我如何衡量它的内存使用情况配置文件？
一般的尾部调用
我分享了另一种在 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关键词？这是摆脱您的功能的方法;在像 JavaScript 这样严格评估的语言中，return <expr>意味着expr中的所有内容都需要在发送结果之前进行计算。
如果expr包含一个子表达式，其函数调用不在尾部位置，则这些调用将引入一个新帧，计算一个中间值，然后将其返回到尾部调用的调用帧 - 这就是为什么如果无法确定何时可以安全地删除堆栈帧，堆栈可能会溢出的原因
无论如何，很难谈论编程，所以希望这个小草图有助于识别一些常见函数中的调用位置。
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在这里坚持一分钟——现在想象一下没有返回值——因为函数无法将值发送回调用方，当然我们可以很容易地推断出在函数被评估后可以立即丢弃所有帧
// 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
延续传递样式
输入延续传递样式 – 通过为每个函数添加一个延续参数，就好像我们发明了自己的返回机制
不要被下面的例子所淹没——大多数人已经看到了这些被误解的东西形式的延续传递风格，称为回调
// 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) })如何获得价值？
这个著名的问题：如何从异步调用返回响应？已经让数百万程序员感到困惑 - 只是，它真的与"异步调用"无关，而与延续以及这些延续是否返回任何内容
有关// nothing can save us...
// unless pythag *returns*
var result = pythag (3,4, ...)
console.log (result) // undefined
如果没有返回值，则必须使用延续将值移动到计算的下一步 - 这不可能是我试图说的第一种方式^^
但一切都在尾部位置！
我知道仅通过查看可能很难分辨，但是每个函数在尾部位置只有一个函数调用– 如果我们在函数中恢复返回功能，则调用 1 的值是调用 2 的值是调用 3 的值，依此类推 – 在这种情况下，无需为后续调用引入新的堆栈帧 – 相反， 呼叫 1 的帧可以重新用于呼叫 2，然后再次用于呼叫 3;我们仍然可以保留返回值！
// 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一般的尾巴呼叫;再次
这种将"正常"函数转换为延续传递样式函数的过程可以是一个机械过程，并且可以自动完成 - 但是将所有内容放入尾部位置的真正意义是什么？
好吧，如果我们知道帧 1 的值是帧 2 的值，也就是帧 3 的值，依此类推，我们可以使用while循环手动折叠堆栈帧，其中计算结果在每次迭代期间就地更新——利用这种技术的函数称为蹦床
当然，在编写递归函数时，蹦床最常被谈论，因为递归函数可以多次"反弹"(生成另一个函数调用);甚至无限期 - 但这并不意味着我们不能在我们的pythag函数上演示一个只会产生几call的蹦床
。
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))呜，你不小心发现了莫纳德
[ 草案 ]
// 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 ] ]当你的递归调用在forEach内部时，你不能优化它，因为为了应用 TCO，编译器需要检查你是否没有保存上一个调用的"状态"。如果forEach，您确实保存了当前位置的"状态"。
为了使用 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中，执行的唯一操作是递归调用，因此，您不会在递归调用之间保存"状态"，因此编译器将应用优化。
递归函数表达得很优雅，尾递归优化甚至可以防止它们吹嘘堆栈。
但是，任何递归函数都可以转换为更丑陋的基于迭代器的解决方案，这可能仅在其内存消耗和性能方面很漂亮，尽管不看。
参见：在 Javascript 中展平第 n 个嵌套数组的迭代解决方案
也许这是对不同方法的测试：https://jsperf.com/iterative-array-flatten/2