A LISP-style PersistentLinkedList would be nice

[sbohmann]

It's the easiest-to-implement persistent data structure, and there are lots of classic functional algorithms that work best when building a list in reverse.

(cons 1 someList)

which creates a new list, starting with 1, followed by the contents of someList, might be e.g. expressed as

someList.prependedBy(1)

or, of course, some better, more concise name.

I'm not good at naming, so I tend to use very obvious, yet also very long, names 😅

[sbohmann]

https://github.com/sbohmann/aoc2024/blob/main/src/main/kotlin/persistentLinkedList/PersistentLinkedList.kt

An example implementation. It is really short due to the simple nature of the data structure.

[chrisjenx]

Interesting, never needed a list built in reverse, where is a common place this would be used?

[kyay10]

Is this truly necessary? It feels like just adding a cons extension would suffice, no? I think linked lists simply have worse performance compared to the implementations in this library. Perhaps what you actually want is a PersistentStack interface that allows for fast consing?

[sbohmann]

You're right, a linked list is not the smartest stack implementation by a long shot. Would be a shame to support those classic algorithms but make them super slow because of using a linked list, which doesn't play nice with cache lines and produced in inordinate amount of garbage 😅
If a persistent stack is already available and fast, that's actually all it takes. A simple, smaller interface is then both easy to make per project as a wrapper or to add to the library 😎

[sbohmann]

@chrisjenx a lot of purely function algorithms have been created during the old LISP days, when linked lists (usually with some kind of direct hardware support) were by far the most common persistent data structures, and they only support last in, first out at reasonable performance.
It actually turned out to be quite practical in recursive algorithms in some cases, and this often carries over to looping and reducing versions, and of course to doing actual recursion using trampoline, which obviously is not as fast as native end recursion optimization.
Btw., JVM, plz add end recursion optimization ^^

[sbohmann]

There's one massive performance advantage in linked lists as compared to tree-bases stacks:
It's extremely cheap to produce a version with one element less, as it does not require path copying - all the work has already been done while building the - admittedly somewhat oversized - data structure. This is especially important for many recursive algorithms.
It also would be a way to tip the head to LISP and the old LISP machines with even hardware support for cons lists.
Plus, as an extra, its simplicity may provide great educational value, because the way it functions is really not distracting from an actual problem at hand 🙂