Purely functional, immutable doubly linked list in JavaScript

Question

In JavaScript, it is trivial to create a pair of nodes that reference each other in an infinite loop:

var node = item => 
    next => 
        previous => {
            return {
                item: item,
                previous: previous,
                next: next
            };
        }; 

var z = {
    a: node('a')(() => z.b)(() => z.b),
    b: node('b')(() => z.a)(() => z.a)
};

Grab either z.a or z.b and you will be able to call next() and previous() infinitely.

Is it possible to instantiate, for instance, for a carousel with any size that can be scrolled in either direction, a circular linked list that can be of an arbitrary number of elements when it is instantiated?

I've read some things from the Haskell Wiki on "Tying the Knot", and found examples in Scala, but I'm not sure how to make these work in JavaScript.

You just did tie the knot using () => z.a before z got defined. — Bergi
– Bergi, Commented Mar 25, 2022 at 10:21
Sorry, I meant I'm not sure how to do this while building up from an array of values! — sent1nel
– sent1nel, Commented Mar 26, 2022 at 5:57

trincot · Accepted Answer · 2022-03-26 09:26:44Z

2

You can use the same principle as you have used for z. Instead of creating an object with two properties a and b, create an array, which will have array indices instead.

var Node = item => 
    next => 
        previous => ({
            item: item,
            previous: previous,
            next: next
        });

var arr = (length =>
    Array.from({length}, (_, i) => 
        Node(i)(() => arr[(i + 1) % length])
               (() => arr[(i + length - 1) % length])
    )
)(4); // IIFE - we want 4 nodes in circular list

// Demo iterating the 4 nodes
var node = arr[0]; // Get one of the nodes
setInterval(() => console.log((node = node.next()).item), 500);

Recursion

Instead of storing the nodes in an array, they could be stored in recursive execution contexts.

For example:

var head = (function CircularList(previous, item, ...items) {
    if (!items.length) return { item, next: () => head, previous };
    var rest = CircularList(() => current, ...items); // Recursion
    var current = { ...rest, previous };
    return { ...rest, item, next: () => current };
})(() => head, 1, 2, 3, 4); // Example: list of four values

// Demo iterations
console.log(head.item);
for (let node = head.next(); node != head; node = node.next()) {
    console.log(node.item);
}
console.log("----");
console.log(head.item);
for (let node = head.previous(); node != head; node = node.previous()) {
    console.log(node.item);
}
console.log("----");

edited Mar 26, 2022 at 9:26

answered Mar 25, 2022 at 7:43

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

sent1nel Over a year ago

Ah, that's an interesting approach. Interestingly, this is very similar to my current approach, admittedly, however, my implementation relies on array slicing more than pointing at indices. Clever. Not quite what I'm looking for though, I am interested to learn of a method, if any currently exists, if it's possible, in which the nodes require no Array.

trincot Over a year ago

"my implementation relies on array slicing more than pointing at indices.": can you clarify? I don't see array slicing.

sent1nel Over a year ago

My personal implementation of a solution to this problem, that does not do the thing I'm interested in, and hence I have not posted. Whose existence is left as an exercise to the reader ;) I solved this problem roughly in the way that you've solved it here, but I am asking more of a theoretical question about a data structure I can imagine, but I'm not sure how to go about instantiating.

trincot Over a year ago

Due to immutability, we know we have to create the nodes all at once -- lazy creation is off the table. This means you need to know the n node references. The most suitable way to know about n references is to have them as an array (or an object with n properties)

sent1nel Over a year ago

That's gnarly. Very cool, yes. Thank you.

|

Collectives™ on Stack Overflow

Purely functional, immutable doubly linked list in JavaScript

1 Answer 1

Recursion

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Recursion

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related