使用蹦床从嵌套数组创建树并将其转换为字符串

Question

我想用 trampoline 在 JavaScript 中重写我的 lisp 中的所有递归函数。我有两个我不知道如何重写的例子：

Pair.fromArray = trampoline(function fromArray(array) {
    if (array.length === 0) {
        return nil;
    } else {
        return new Thunk(() => {
            var car;
            if (array[0] instanceof Array) {
                car = Pair.fromArray(array[0]);
            } else {
                car = array[0];
            }
            if (typeof car === 'string') {
                car = LString(car);
            }
            if (array.length === 1) {
                return new Pair(car, nil);
            } else {
                // this overload the stack
                return new Pair(car, Pair.fromArray(array.slice(1)));
            }
        });
    }
});

// ----------------------------------------------------------------------
var pair_to_string = trampoline(function pair_to_string(pair, rest) {
    var arr = [];
    if (!rest) {
        arr.push('(');
    }
    var value = toString(pair.car, true);
    if (value !== undefined) {
        arr.push(value);
    }
    return new Thunk(() => {
        if (pair.cdr instanceof Pair) {
            arr.push(' ');
            const cdr = pair_to_string(pair.cdr, true);
            arr.push(cdr);
        } else if (pair.cdr !== nil) {
            arr = arr.concat([' . ', toString(pair.cdr, true)]);
        }
        if (!rest) {
            arr.push(')');
        }
        return arr.join('');
    });
});

// ----------------------------------------------------------------------
Pair.prototype.toString = function(quote, rest) {
    return pair_to_string(this, quote, rest);
};

这是蹦床代码：

function Thunk(fn) {
    this.fn = fn;
}
// ----------------------------------------------------------------------
Thunk.prototype.toString = function() {
    return '#<Thunk>';
};
// ----------------------------------------------------------------------
function trampoline(fn) {
    return function(...args) {
        return unwind(fn.apply(this, args));
    };
}
// ----------------------------------------------------------------------
function unwind(result) {
    while (result instanceof Thunk) {
        result = result.fn();
    }
    return result;
}

问题是它不起作用，如果从 trampoline 调用中调用 trampolined 函数 return 值，它会使堆栈过载，当我调用命名函数表达式时，我得到：(1 #<Thunk>).我试过放置 unwind(pair_to_string(pair.cdr, quote, true)) 但这也会使堆栈超载。

这个函数可以用 trampoline 编写，以便将 lisp 列表转换为字符串吗？

这是包含两个函数的 Stack 片段。我知道我需要编写看起来像尾递归的函数，但是 return Thunk 但是如果我在创建表达式的过程中我该怎么做。

// ----------------------------------------------------------------------
function Thunk(fn) {
    this.fn = fn;
}
// ----------------------------------------------------------------------
Thunk.prototype.toString = function() {
    return '#<Thunk>';
};
// ----------------------------------------------------------------------
function trampoline(fn) {
    return function(...args) {
        return unwind(fn.apply(this, args));
    };
}
// ----------------------------------------------------------------------
function unwind(result) {
    while (result instanceof Thunk) {
        result = result.fn();
    }
    return result;
}
// ----------------------------------------------------------------------
function toString(obj, ...arg) {
  if (obj instanceof Pair) {
      return obj.toString(...arg);
  }
  return obj.toString();
}
// ----------------------------------------------------------------------
function Pair(car, cdr) {
  this.cdr = cdr;
  this.car = car;
}
// ----------------------------------------------------------------------
var nil = new function Nil() {};
// ----------------------------------------------------------------------
Pair.fromArray = trampoline(function fromArray(array) {
    if (array.length === 0) {
        return nil;
    } else {
        var car;
        if (array[0] instanceof Array) {
            car = Pair.fromArray(array[0]);
        } else {
            car = array[0];
        }
        if (array.length === 1) {
            return new Pair(car, nil);
        } else {
            return new Pair(car, Pair.fromArray(array.slice(1)));
        }
    }
});
// ----------------------------------------------------------------------
var pair_to_string = function pair_to_string(pair, rest) {
    var arr = [];
    if (!rest) {
        arr.push('(');
    }
    var value = toString(pair.car, true);
    if (value !== undefined) {
        arr.push(value);
    }
    if (pair.cdr instanceof Pair) {
        arr.push(' ');
        const cdr = pair_to_string(pair.cdr, true);
        arr.push(cdr);
    } else if (pair.cdr !== nil) {
        arr = arr.concat([' . ', toString(pair.cdr, true)]);
    }
    if (!rest) {
        arr.push(')');
    }
    return arr.join('');
};

// ----------------------------------------------------------------------
Pair.prototype.toString = function(rest) {
    return pair_to_string(this, rest);
};

// ----------------------------------------------------------------------
function range(n) {
    const range = new Array(n).fill(0).map((_, i) => i);
    return Pair.fromArray(range);
}

// ----------------------------------------------------------------------
console.log(range(40).toString());
var l = range(8000);
console.log(l.toString());

注意：以上代码重构了原始功能，没有任何蹦床（包括但未使用蹦床代码）。

PS：我也很喜欢其他解决方案，它允许在不使用递归的情况下遍历二叉树并消耗堆栈。如果您不能使用蹦床遍历二叉树，我也可以解释为什么这是不可能的。但更喜欢实际的解决方案。

Answer 1

嵌套蹦床

您已突出显示问题 -

Pair.fromArray = trampoline(function(array) {
  if ...
    return ...
  else
    return new Thunk(() => {
      if ...
        ...
      else
        return new Pair(car, Pair.fromArray(array.slice(1))) // !
      })
  }
});

Pair.fromArray 是 trampoline(function() { ... })，对 Pair.fromArray 的递归调用创建了一个嵌套进程 -

Pair.fromArray([1, 2, 3])
unwind(fn.apply(this, [1, 2, 3]))
unwind(new Thunk(() => ...))
unwind(new Pair(1, Pair.fromArray([2, 3])))
unwind(new Pair(1, unwind(fn.apply(this, [2, 3]))))
unwind(new Pair(1, unwind(new Thunk(() => ...))))
unwind(new Pair(1, unwind(new Pair(2, Pair.fromArray([3])))))
unwind(new Pair(1, unwind(new Pair(2, unwind(fn.apply(this, [3]))))))
unwind(new Pair(1, unwind(new Pair(2, unwind(new Thunk(() => ...))))))
unwind(new Pair(1, unwind(new Pair(2, unwind(new Pair(3, nil))))))
unwind(new Pair(1, unwind(new Pair(2, new Pair(3, nil)))))
unwind(new Pair(1, new Pair(2, new Pair(3, nil))))
new Pair(1, new Pair(2, new Pair(3, nil)))

正如你所看到的，每个元素嵌套了另一帧unwind，直到遇到输入数组的末尾才能关闭。

可能的实现

让我们概述一个小程序来创建一个包含 100 个元素的 Lisp-style 列表 -

import { fromArray, toString } from "./List"


console.log(toString(fromArray([[1,[2,3],4,[],5]])))
console.log(toString(fromArray(Array.from(Array(100), (_, v) => v))))

预期输出 -

((1 (2 3) 4 () 5))
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100)

我们可以用任何方式写List。这是一种方式 -

// List.js

import { Pair } from "./Pair"
import { Loop, Recur } from "./TailRec"

function push(r, v)
{ r.push(v)
  return r
}

const Nil =
  Symbol()

const fromArray = (a = []) =>
  Loop(function(r = Nil, i = 0) {
    if (i >= a.length)
      return reverse(r)
    else if (Array.isArray(a[i]))
      return Recur(Pair(fromArray(a[i]), r), i + 1) 
    else
      return Recur(Pair(a[i], r), i + 1)
  })

const toString = (t = Nil) =>
  Loop(function(r = [], m = t) {
    if (m === Nil)
      return "(" + r.join(" ") + ")"
    else if (m.car === Nil || m.car instanceof Pair)
      return Recur(push(r, toString(m.car)), m.cdr)
    else 
      return Recur(push(r, m.car), m.cdr)
  })

const reverse = (t = Nil) =>
  Loop(function(r = Nil, m = t) {
    if (m === Nil)
      return r
    else
      return Recur(Pair(m.car, r), m.cdr)
  })

export { fromArray, reverse, toString }

这是 Pair 模块 -

// Pair.js

function Pair (car, cdr)
{ return Object.create
    ( Pair.prototype
    , { constructor: { value: Pair }
      , car: { value: car }
      , cdr: { value: cdr }
      }
    )
}

export { Pair }

和TailRec模块-

// TailRec.js

function Loop (f, ...init)
{ let r = f(...init)
  while (r instanceof Recur)
    r = f(...r)
  return r
}

function Recur (...v)
{ return Object.create
    ( Recur.prototype
    , { constructor: { value: Recur }
      , [Symbol.iterator]: { value: _ => v.values() }
      }
    )
}

export { Loop, Recur }

运行下面的代码片段构建了一个包含 100,000 个元素的 Lisp-style 列表 -

function push(r, v)
{ r.push(v)
  return r
}

function Pair (car, cdr)
{ return Object.create
    ( Pair.prototype
    , { constructor: { value: Pair }
      , car: { value: car }
      , cdr: { value: cdr }
      }
    )
}

function Loop (f, ...init)
{ let r = f(...init)
  while (r instanceof Recur)
    r = f(...r)
  return r
}

function Recur (...v)
{ return Object.create
    ( Recur.prototype
    , { constructor: { value: Recur }
      , [Symbol.iterator]: { value: _ => v.values() }
      }
    )
}

const Nil =
  Symbol()

const fromArray = (a = []) =>
  Loop(function(r = Nil, i = 0) {
    if (i >= a.length)
      return reverse(r)
    else if (Array.isArray(a[i]))
      return Recur(Pair(fromArray(a[i]), r), i + 1) 
    else
      return Recur(Pair(a[i], r), i + 1)
  })

const toString = (t = Nil) =>
  Loop(function(r = [], m = t) {
    if (m === Nil)
      return "(" + r.join(" ") + ")"
    else if (m.car === Nil || m.car instanceof Pair)
      return Recur(push(r, toString(m.car)), m.cdr)
    else 
      return Recur(push(r, m.car), m.cdr)
  })

const reverse = (t = Nil) =>
  Loop(function(r = Nil, m = t) {
    if (m === Nil)
      return r
    else
      return Recur(Pair(m.car, r), m.cdr)
  })

console.log(toString(fromArray([[1,[2,3],4,[]]])))
console.log(toString(fromArray(Array.from(Array(100000), (_, v) => v))))

继续阅读...

如您所见，这适用于巨大的列表，但是如果您需要创建非常深的嵌套列表，仍然有可能破坏堆栈。您可以编写任何递归程序 stack-safe 而无需 改变您对它的看法。在 . To see Loop and Recur demonstrated in other ways, see these Q&As.

中了解有关此类技术的更多信息

健壮，像 lisp

如前所述，当对嵌套很深的数组调用 fromArray 时，上面的代码会溢出堆栈。如果 toString 试图将深度嵌套的列表转换为字符串，则同样如此。 Lisp 列表没有这些限制，所以让我们做一些改进 -

// Main.js

import { fromArray, toString } from "./List"

// create a deeply nested list!
let r = ["hi"]
for (let i = 0; i < 20000; i++)
  r = [r]

console.log(toString(fromArray(r)))

我们希望看到 (...) 嵌套 20,000 层深 -

((((((((...((((((((hi))))))))...))))))))

这次我们将使用更复杂的 TailRec 模块来实现我们的 List 模块 -

// List.js

import { loop, recur, call } from "./TailRec"
import { pair, isPair } from "./Pair"

const nil =
  Symbol("nil")

const isNil = t =>
  t === nil

const isList = t =>
  isNil(t) || isPair(t)

const push = (r, v) =>
  (r.push(v), r)

const fromArray = (a = []) =>
  loop
    ( ( m = a
      , i = 0
      ) =>
        i >= m.length
          ? nil
          : call
              ( pair
              , Array.isArray(m[i])
                  ? recur(m[i], 0)
                  : m[i]
              , recur(m, i + 1)
              )
    )

const toString = (t = nil) =>
  loop
    ( ( m = t
      , r = []
      ) =>
        isNil(m)
          ? "(" + r.join(" ") + ")"
      : recur
          ( m.cdr
          , call
              ( push
              , r
              , isList(m.car)
                  ? recur(m.car, [])
                  : String(m.car)
              )
          )
    )

export { fromArray, toString }

采用中介绍的技术，我们实现了一个 TailRec 模块。重要的是要注意这可以解决您的特定问题而无需更改原始模块 -

// TailRec.js

const call = (f, ...values) => ...

const recur = (...values) => ...

const loop = f => ...

const run = r => ...

export { loop, recur, call }

最后是用于构建列表的 Pair 模块 -

// Pair.js

class Pair
{ constructor (car, cdr)
  { this.car = car
  ; this.cdr = cdr
  }
}

const pair = (car, cdr) =>
  new Pair(car, cdr)

const isPair = t =>
  t instanceof Pair

const toString = t =>
  `(${t.car} . ${t.cdr})`

export { pair, isPair, toString }

展开下面的代码片段以在浏览器中验证结果 -

const call = (f, ...values) =>
  ({ type: call, f, values })

const recur = (...values) =>
  ({ type: recur, values })

const identity = x =>
  x

const loop = f =>
{ const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? call (aux, expr.values, values => call (aux1, f (...values), k))
  : expr.type === call
      ? call (aux, expr.values, values => call (aux1, expr.f (...values), k))
  : call (k, expr)

  const aux = (exprs = [], k) =>
    call
      ( exprs.reduce
          ( (mr, e) =>
              k => call (mr, r => call (aux1, e, x => call (k, [ ...r, x ])))
          , k => call (k, [])
          )
      , k
      )

  return run (aux1 (f ()))
}

const run = r =>
{ while (r && r.type === call)
    r = r.f (...r.values)
  return r
}

class Pair
{ constructor (car, cdr)
  { this.car = car
  ; this.cdr = cdr
  }
}

const pair = (car, cdr) =>
  new Pair(car, cdr)

const isPair = t =>
  t instanceof Pair

const nil =
  Symbol("nil")

const isNil = t =>
  t === nil

const isList = t =>
  isNil(t) || isPair(t)

const push = (r, v) =>
  (r.push(v), r)

const fromArray = (a = []) =>
  loop
    ( ( m = a
      , i = 0
      ) =>
        i >= m.length
          ? nil
          : call
              ( pair
              , Array.isArray(m[i])
                  ? recur(m[i], 0)
                  : m[i]
              , recur(m, i + 1)
              )
    )

const toString = (t = nil) =>
  loop
    ( ( m = t
      , r = []
      ) =>
        isNil(m)
          ? "(" + r.join(" ") + ")"
      : recur
          ( m.cdr
          , call
              ( push
              , r
              , isList(m.car)
                  ? recur(m.car, [])
                  : String(m.car)
              )
          )
    )


let a = ["hi"]
for (let i = 0; i < 20000; i++)
  a = [a]

document.body.textContent = toString(fromArray(a))
// ((((((((...((((((((hi))))))))...))))))))

body { overflow-wrap: anywhere; }

Answer 2

这就是我要做的。

// range :: Number -> List Number
const range = n => enumFromTo(0, n - 1);

// enumFromTo :: (Number, Number) -> List Number
const enumFromTo = (m, n) => m > n ? null : {
    head: m,
    get tail() {
        return enumFromTo(m + 1, n);
    }
};

// showList :: List Number -> String
const showList = xs => xs === null ? "()" :
    `(${showListElements(xs.head, xs.tail)})`;

// (Number, List Number) -> String
const showListElements = (x, xs) => {
    let string = `${x}`;
    let variant = xs;

    while (variant !== null) {
        const { head, tail } = variant;
        string = `${string} ${head}`;
        variant = tail;
    }

    return string;
};

console.log(showList(range(40)));
console.log(showList(range(8000)));

如您所见，您根本不需要蹦床。你唯一需要的就是懒惰。

您可能还会发现以下 Stack Overflow 线程很有趣。

Answer 3

我能够为递归函数创建解决方案，该函数需要在蹦床递归后通过使用延续来做一些事情。如果没有 Thunk 中的延续，就无法将 ) 作为列表的结尾。需要在trampoline结束时调用，但需要在返回Thunk时指定代码。

当列表嵌套非常bing时，这可能会引发堆栈溢出错误，但我认为对于我的情况来说没问题。它适用于 range(8000) 并且适用于嵌套列表，所以这没问题。

function Pair(car, cdr) {
  this.car = car;
  this.cdr = cdr;
}
const nil = new function Nil() {};

// ----------------------------------------------------------------------
Pair.fromArray = function(array) {
    var result = nil;
    var i = array.length;
    while (i--) {
        let car = array[i];
        if (car instanceof Array) {
            car = Pair.fromArray(car);
        }
        result = new Pair(car, result);
    }
    return result;
};

// ----------------------------------------------------------------------
function Thunk(fn, cont = () => {}) {
    this.fn = fn;
    this.cont = cont;
}

// ----------------------------------------------------------------------
Thunk.prototype.toString = function() {
    return '#<Thunk>';
};

// ----------------------------------------------------------------------
function trampoline(fn) {
    return function(...args) {
        return unwind(fn.apply(this, args));
    };
}

// ----------------------------------------------------------------------
function unwind(result) {
    while (result instanceof Thunk) {
        const thunk = result;
        result = result.fn();
        if (!(result instanceof Thunk)) {
            thunk.cont();
        }
    }
    return result;
}

// ----------------------------------------------------------------------
function toString(x) {
  return x.toString();
}

// ----------------------------------------------------------------------
const pair_to_string = (function() {
    const prefix = (pair, rest) => {
        var result = [];
        if (pair.ref) {
            result.push(pair.ref + '(');
        } else if (!rest) {
            result.push('(');
        }
        return result;
    };
    const postfix = (pair, rest) => {
        if (!rest || pair.ref) {
            return [')'];
        }
        return [];
    };
    return trampoline(function pairToString(pair, quote, extra = {}) {
        const {
            nested,
            result = [],
            cont = () => {
                result.push(...postfix(pair, nested));
            }
        } = extra;
        result.push(...prefix(pair, nested));
        let car;
        if (pair.cycles && pair.cycles.car) {
            car = pair.cycles.car;
        } else {
            car = toString(pair.car, quote, true, { nested: false, result, cont });
        }
        if (car !== undefined) {
            result.push(car);
        }
        return new Thunk(() => {
            if (pair.cdr instanceof Pair) {
                if (pair.cycles && pair.cycles.cdr) {
                    result.push(' . ');
                    result.push(pair.cycles.cdr);
                } else {
                    if (pair.cdr.ref) {
                        result.push(' . ');
                    } else {
                        result.push(' ');
                    }
                    return pairToString(pair.cdr, quote, {
                        nested: true,
                        result,
                        cont
                    });
                }
            } else if (pair.cdr !== nil) {
                result.push(' . ');
                result.push(toString(pair.cdr, quote));
            }
        }, cont);
    });
})();

// ----------------------------------------------------------------------
Pair.prototype.toString = function(quote) {
    var result = [];
    pair_to_string(this, quote, {result});
    return result.join('');
};

// ----------------------------------------------------------------------
function range(n) {
    return new Array(n).fill(0).map((_, i) => i);
}

// ----------------------------------------------------------------------
console.log(Pair.fromArray([[[range(8000), range(10)]]]).toString());

使用蹦床从嵌套数组创建树并将其转换为字符串

Using trampoline to create tree from nested arrays and covert that to string

javascript

recursion

stack-overflow

trampolines