基于蹦床的链表(lisp 树)到带循环的字符串 [英] Trampoline based linked list (lisp tree) to string with cycles

问题描述

我的基于蹦床的函数有问题，该函数将 lisp 列表字符串化.代码如下:

I have problem with my trampoline based function that stringify lisp list. Here is the code:

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;
}

// ----------------------------------------------------------------------
// original function have different data types here
// with simplified version this is fine
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);
}

// ----------------------------------------------------------------------------
function markCycles(pair) {
    var seen_pairs = [];
    var cycles = [];
    var refs = [];
    function visit(pair) {
        if (!seen_pairs.includes(pair)) {
            seen_pairs.push(pair);
        }
    }
    function set(node, type, child, parents) {
        if (child instanceof Pair) {
            if (parents.includes(child)) {
                if (!refs.includes(child)) {
                    refs.push(child);
                }
                if (!node.cycles) {
                    node.cycles = {};
                }
                node.cycles[type] = child;
                if (!cycles.includes(node)) {
                    cycles.push(node);
                }
                return true;
            }
        }
    }
    const detect = trampoline(function detect_thunk(pair, parents) {
        if (pair instanceof Pair) {
            delete pair.ref;
            delete pair.cycles;
            visit(pair);
            parents.push(pair);
            var car = set(pair, 'car', pair.car, parents);
            var cdr = set(pair, 'cdr', pair.cdr, parents);
            var thunks = [];
            if (!car) {
                detect(pair.car, parents.slice());
            }
            if (!cdr) {
                const cdr_args = [pair.cdr, parents.slice()];
                return new Thunk(() => {
                    return detect_thunk(...cdr_args);
                });
            }
        }
    });
    function mark_node(node, type) {
        if (node.cycles[type] instanceof Pair) {
            const count = ref_nodes.indexOf(node.cycles[type]);
            node.cycles[type] = `#${count}#`;
        }
    }
    detect(pair, []);
    var ref_nodes = seen_pairs.filter(node => refs.includes(node));
    ref_nodes.forEach((node, i) => {
        node.ref = `#${i}=`;
    });
    cycles.forEach(node => {
        mark_node(node, 'car');
        mark_node(node, 'cdr');
    });
}
// ----------------------------------------------------------------------
// this works fine
//console.log(Pair.fromArray([[[range(8000), range(10)]]]).toString());
var data = new Pair(1, new Pair(new Pair(2, nil), new Pair(3, nil)));
data.cdr.car.cdr = data.cdr;
data.cdr.cdr.cdr = data;
markCycles(data)
console.log(data.toString());
console.log("#0=(1 . #1=((2 . #1#) 3 . #0#)) - valid");

问题是缺少最后一个括号，我不确定我应该如何在蹦床中使用延续来解决这个问题.

The problem is the last parenthesis is missing, I'm not sure how I should use continuation in trampoline to fix the issue.

这是没有蹦床的代码:

// ----------------------------------------------------------------------
Pair.prototype.toString = function(quote, rest) {
    var arr = [];
    if (this.ref) {
        arr.push(this.ref + '(');
    } else if (!rest) {
        arr.push('(');
    }
    var value;
    if (this.cycles && this.cycles.car) {
        value = this.cycles.car;
    } else {
        value = toString(this.car, quote, true);
    }
    if (value !== undefined) {
        arr.push(value);
    }
    if (this.cdr instanceof Pair) {
        if (this.cycles && this.cycles.cdr) {
            arr.push(' . ');
            arr.push(this.cycles.cdr);
        } else {
            if (this.cdr.ref) {
                arr.push(' . ');
            } else {
                arr.push(' ');
            }
            const cdr = this.cdr.toString(quote, true);
            arr.push(cdr);
        }
    } else if (this.cdr !== nil) {
        arr = arr.concat([' . ', toString(this.cdr, quote, true)]);
    }
    if (!rest || this.ref) {
        arr.push(')');
    }
    return arr.join('');
};

我有两种情况应该首先使用大列表(8000 个元素)和小循环.使用堆栈片段中的代码，它可以处理长列表，但不能处理没有蹦床的循环，它会溢出大列表上的堆栈.它也是 lisp，所以它需要处理任何树，而不仅仅是链表.

I have two cases that should work first big list (8000 elements) and small cycle. With the code in stack snippet it work with long list but not with cycles without the trampoline it overflow the stack on big list. Also it's lisp so it need to work any any tree not only linked list.

编辑:如果您尝试回答，请至少不要更改数据结构.它需要与 car 和 cdr 是 Pair 类，并且需要在将它们转换为字符串之前计算周期.因此它可以与多个检查内存中的数据是否为循环的函数配合使用.

EDIT: if you try to answer please at least don't change the data structures. It need to be Pair class with car and cdr and cycles need to be calculated before they are converted to string. So it work with multiple functions that check if data in memory is cycle.

推荐答案

这就是我会做的.

const pure = value => ({ constructor: pure, value });

const bind = (monad, arrow) => ({ constructor: bind, monad, arrow });

const thunk = eval => ({ constructor: thunk, eval });

function evaluate(expression) {
    let expr = expression;
    let stack = null;

    while (true) {
        switch (expr.constructor) {
            case pure:
                if (stack === null) return expr.value;
                expr = stack.arrow(expr.value);
                stack = stack.stack;
                break;
            case bind:
                stack = { arrow: expr.arrow, stack };
                expr = expr.monad;
                break;
            case thunk:
                expr = expr.eval();
        }
    }
}

const monadic = func => thunk(() => {
    const gen = func();

    function next(data) {
        const { value, done } = gen.next(data);
        return done ? value : bind(value, next);
    }

    return next(undefined);
});

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

    static fromArray(array) {
        const loop = (array, index) => monadic(function* () {
            if (index === array.length) return pure(null);
            const item = array[index];
            const car = Array.isArray(item) ? yield loop(item, 0) : item;
            const cdr = yield loop(array, index + 1);
            return pure(new Pair(car, cdr));
        });

        return evaluate(loop(array, 0));
    }

    duplicates() {
        const visited = new WeakSet();
        const result = new WeakSet();

        const loop = pair => monadic(function* () {
            if (visited.has(pair)) {
                result.add(pair);
            } else {
                visited.add(pair);
                const { car, cdr } = pair;
                if (car instanceof Pair) yield loop(car);
                if (cdr instanceof Pair) yield loop(cdr);
            }

            return pure(result);
        });

        return evaluate(loop(this));
    }

    toString() {
        let result = "";

        const duplicates = this.duplicates();
        const visited = [];

        const loop = (pair, end) => monadic(function* () {
            const index = visited.indexOf(pair);

            if (index < 0) {
                const duplicate = duplicates.has(pair);

                if (duplicate) {
                    const last = visited.push(pair) - 1;
                    result += end ? ` . #${last}=(` : `#${last}=(`;
                } else result += end ? " " : "(";

                const { car, cdr } = pair;

                if (car instanceof Pair) yield loop(car, false);
                else result += JSON.stringify(car);

                if (cdr instanceof Pair) yield loop(cdr, true);
                else if (cdr === null) result += ")";
                else result += ` . ${JSON.stringify(cdr)})`;

                if (duplicate && end) result += ")";
            } else {
                result += end ? ` . #${index}#)` : `#${index}#`;
            }

            return pure(result);
        });

        return evaluate(loop(this, false));
    }
}

const data = new Pair(1, new Pair(new Pair(2, null), new Pair(3, null)));
data.cdr.car.cdr = data.cdr;
data.cdr.cdr.cdr = data;

console.log(data.toString());

const range = length => Array.from({ length }, (x, i) => i);

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

希望有所帮助.

这篇关于基于蹦床的链表(lisp 树)到带循环的字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！