Javascript递归数据结构定义

Question

我需要在 Javascript 中递归地定义一个数据结构。这是一个循环链表的简单示例:

// List a very simplified example of what the actual (non list) code does.
function List(f, r) {
    return function(){ return [f, r]; };
}

var first = function (l){ return l()[0]; }
var rest = function (l){ return l()[1]; }

var head = List('a', List('b', List('c', head)));

执行此操作时，列表“c”中的头被解析为未定义，而不是我需要的列表“a”。 List 是一个返回函数的示例函数(它不是我可以附加到的 Javascript 列表)。

我试图将 head 的定义包装为一个自执行的命名函数，但是当 head 被解析时，堆栈崩溃了。

我忽略的 Javascript 风格解决方案是什么？

<小时/>

尝试

闲逛，我想出了一些可能有效的代码:

var f = function(){
    var value;
    return function(v){
        if (value === undefined)
            value = v
        return value.apply(undefined, arguments);
    };
};

var tempHead = f();
var head = List('a', List('b', List('c', tempHead)));
tempHead(head);

first(head); // a
first(rest(head)) // b
first(rest(rest(head))) // c
first(rest(rest(rest(head)))) // a
first(rest(rest(rest(rest(head))))) // b
...

但这真的很丑。还有更好的解决方案吗？

<小时/>

解决方案

user1689607 提出了一个很好的解决方案，我将其封装以隐藏一些实现:

var def = function(name, impl) {
    var value;
    return value = impl.apply(Object.defineProperty({}, name, {
       'value': function() { return value.apply(this, arguments); }
    }));
};

function List(f, r) {
    return function(){ return [f, r]; };
}

function first(l){ return l()[0]; }
function rest(l){ return l()[1]; }

var circle = def('head', function() {
    return List('a', List('b', List('c', this.head)));
});

first(circle); // 'a'
first(rest(circle)); // 'b'
first(rest(rest(circle))); // 'c'
first(rest(rest(rest(circle)))); // 'a'
first(rest(rest(rest(rest(circle))))); // 'b'

<小时/>

还有一个更新，我最终明确地传递自引用而不是更改范围:

var def = function(impl) {
    var value;
    return (value = impl(function() { return value.apply(this, arguments); }));
};

var circle = def(function(self) {
    return List('a', List('b', List('c', self)));
});

此代码用于 parse.js 。

Answer 1

这就是你想要的吗？

var headCaller = function() { return head.apply(this, arguments); };

var head = List('a', List('b', List('c', headCaller)));

它给出了您想要的结果...

演示: http://jsfiddle.net/ruNY3/

var results = [
    first(head), // a
    first(rest(head)), // b
    first(rest(rest(head))), // c
    first(rest(rest(rest(head)))), // a
    first(rest(rest(rest(rest(head))))) // b
];

<小时/>

[
    "a",
    "b",
    "c",
    "a",
    "b"
]