I need to define a data structure recursively in Javascript. Here is a simple example of a circular linked list:
// 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)));
When this is executed, head in List 'c' is resolved to undefined, not List 'a' as I need. List is an example function that returns a function (It is not an Javascript list that I can append to).
I tried to wrap the definition of head is a self executing named function, but that blew the stack when head was resolved.
What is the Javascript style solution that I am overlooking?
Attempt
Fooling around, I came up with some code that may work:
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
...
But this is really ugly. Any better solutions?
Solution
user1689607 came up with a good solution which I have encapsulated to hide some of the implementation:
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'
One more update, I ended up going with passing the self reference explicitly instead of changing the scope:
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)));
});
This code is used in parse.js.
head
will be passed to the innermost function call. Becausehead
's value will be evaluated before any of theList
functions are called, and therefore before any assignment can be done tohead
, its value will beundefined
.undefined
. What do you want it to be instead? Better yet, could you add your desired value forhead
?