StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POJavascript recursive data structure definition
text
Body
copied!<p>I need to define a data structure recursively in Javascript. Here is a simple example of a circular linked list:</p> <pre><code>// 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))); </code></pre> <p>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).</p> <p>I tried to wrap the definition of head is a self executing named function, but that blew the stack when head was resolved.</p> <p>What is the Javascript style solution that I am overlooking?</p> <hr> <p><strong>Attempt</strong></p> <p>Fooling around, I came up with some code that may work:</p> <pre><code>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 ... </code></pre> <p>But this is really ugly. Any better solutions?</p> <hr> <p><strong>Solution</strong></p> <p>user1689607 came up with a good solution which I have encapsulated to hide some of the implementation:</p> <pre><code>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' </code></pre> <hr> <p>One more update, I ended up going with passing the self reference explicitly instead of changing the scope:</p> <pre><code>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))); }); </code></pre> <p>This code is used in <a href="https://github.com/mattbierner/parse.js" rel="nofollow">parse.js</a>. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload