JavaScript 中的纯函数式、不可变双向链表

Question

在JavaScript中，创建一对在无限循环中相互引用的节点是微不足道的：

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)
};

抓住 z.a 或 z.b，您将能够无限调用 next() 和 previous()。

是否可以实例化，比如任意大小的旋转木马，可以在任意方向滚动，实例化时可以是任意数量元素的循环链表？

我已经从 Haskell Wiki 上的“打结”中阅读了一些内容，并在 Scala 中找到了示例，但我不确定如何在 JavaScript 中实现这些示例。

Answer 1

您可以使用与 z 相同的原则。与其创建具有两个属性 a 和 b 的对象，不如创建一个数组，该数组将具有数组索引。

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);

递归

与其将节点存储在数组中，不如将它们存储在递归执行上下文中。

例如：

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("----");

JavaScript 中的纯函数式、不可变双向链表

Purely functional, immutable doubly linked list in JavaScript

javascript

functional-programming

doubly-linked-list

递归