1

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.

7
  • 1
    What is the source code for the List function?
    – dtbarne
    Commented Nov 10, 2012 at 16:47
  • 2
    JavaScript doesn't have pointers. No matter what, the current value of head will be passed to the innermost function call. Because head's value will be evaluated before any of the List functions are called, and therefore before any assignment can be done to head, its value will be undefined. Commented Nov 10, 2012 at 16:50
  • Added an example list function. Remember, this is only a very simple example. Commented Nov 10, 2012 at 16:59
  • You need to have a seed value for recursion. Right now it is undefined. What do you want it to be instead? Better yet, could you add your desired value for head? Commented Nov 10, 2012 at 17:08
  • I understand when variables are resolved and that Javascript does not have pointers, I am trying to get around those restrictions. The List c 'head' tail value should be set to a value that transparently resolves itself to the defined value of head when called. Commented Nov 10, 2012 at 17:19

3 Answers 3

1

This is what you want?

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

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

It gives the result you seem to want...

DEMO: 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"
]
2
  • This looks right. Good call that I dont need all the value storage stuff from the example since head is resolved when headCaller is called. I will add a note to the question that encapsulates this logic. Commented Nov 10, 2012 at 18:05
  • @MattBierner: Yeah, that's the beauty of closures. The headCaller will always read the current value of head. Of course you can pass the function directly if you don't want the variable, and you can shorten it there's no arguments to pass and no this value to maintain. function() { return head(); } Commented Nov 10, 2012 at 18:08
0

I am not sure if this is what you want, check it:

function List(f, r) {
    var fr = [f, r];
    var func = function() {
        return fr;
    };
    func.fr = fr; // because that is a reference we can trick it
    return func;
}

var head = List('a', List('b', List('c', null)));
head.fr[1].fr[1].fr[1] = head; // make a loop

Added: a function to do it more easily

// Or this method for lazy people
function createCircularList(f) {
    var head = List(f[f.length - 1], null);
    var firstfr = head.fr;
    for (var i = f.length - 2; i >= 0; i--) {
        head = List(f[i], head);
    }
    firstfr[1] = head;
    return head;
}

var head = createCircularList(['a', 'b', 'c']);

Demo: http://jsfiddle.net/alvinhochun/5nmpR/

In JavaScript, things are interesting. Everything is references, yet the reference itself is a value.

var a = [0, 0];    // `a` is set to the reference of `[0, 0]`
var b = a;         // `b` refers to the same thing as `a`
console.log(b[0]); // shows 0
a[0] = 1;          // it modifies the object that it references to
console.log(b[0]); // shows 1
a = [2, 0];        // a new reference is assigned to `a`
console.log(b[0]); // still shows 1
0

When you give head in parameter, it's not yet assigned. You need to use two steps. Also, there is no need to use nested functions.

function List(f, r) {
    return { value: f, next: r};
}

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

In Javascript, there are no pointer, but all Array or Object are assigned by reference.


EDIT:

A solution for make it simpler:

function List(f) {
    var list = { value: f, next: null };
    list.next = list;
    return list;
}

function insert(list, elm) {
    list.next = { next: list.next, value: elm };
}

function forward(list, nb) {
    for (var current = list; nb > 0; nb--)
        current = current.next;
    return current;
}

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

console.log(head.value); //a
console.log(head.next.value); //b
console.log(head.value); //c

console.log(forward(head, 3));//a
1
  • List is only an example function that will always return a function. I cannot access parameters on it. Commented Nov 10, 2012 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.