Any plans for a list/vector? about immutables HOT 10 OPEN

The immutable list type will be quite similar to Python's tuple type. But, tuple + tuple is an O(n) operation, while extending an immutable list (or concatenating two immutable lists) will be a (O log32 N) operation.

from immutables.

Not in the foreseeable future, unfortunately. PRs are welcome, though :)

from immutables.

How would an immutable list type differ from Python's tuple?

from immutables.

Not in the foreseeable future, unfortunately. PRs are welcome, though :)

I would like to work on this. I think about an implementation using fingertrees. Any advice?

from immutables.

I would like to work on this.

Great!

I think about an implementation using fingertrees. Any advice?

Is that what say Clojure uses? The current HAMT implementation was hugely inspired by Clojure's map implementation, so it would be great to study how they handle vectors.

from immutables.

HAMT is mostly the preferred way to implement mapping with Scheme.

I am not very familiar with Clojure. I found about that library https://github.com/clojure/data.finger-tree.

I investigated, and asked for advice around. finger trees have a good amortized complexity. The important word is "amortized", in other words it is a hit or miss in terms of performance if you randomly get something in the middle of the list. AFAIU, only the beginning and the end of the list can have predictable performance. Finger-trees were invented around Haskell that has great facility for delayed computation, it is optimized for that, since the default behavior is lazy. And AFAIK / AFAIU it is different with Python (it is possible, but not optimized). Finger trees are said to be a generic toolkit to create immutable data structures, is not false, but it requires at the very least benchmarks to be able to tell whether it is useful in practice.

I was said to go with a binary-tree with a log measure to implement an indexed immutable list. The problem with that approach is that it is very mathy stuff, or hackish. It sound to me like a hack similar to how to compute a hash in the implementation of an hash-table. The advantage is that it is easier to implement than finger trees. Also, the research debate is focused on the measure used tell whether the tree is balanced or not, ie. changing the measure (which happened twice over a couple of decades), is backward compatible and easy to do.

Also, the binary search tree approach allows to implement ordered mappings 💌.

I am not sure whether I will do it. I will post here if/when I have something useful.

from immutables.

@amirouche sounds good. Although let me explicitly say that I wouldn't want to replace the current HAMT implementation for maps with something else. Using new algos to implement new types should be OK though.

from immutables.

pyrsistent is a full-featured python immutable data structure library. It has a persistent vector type implemented in C. It's funny that pyrsistent lacks a C versioned map type(Its immutable map is implemented in python). Seems pyrsistent and immutables can complete each other.

from immutables.

I started implementing ordered mappings at https://github.com/amirouche/lbst/blob/c6c913a68d02108a106382543f9648d3f4a3be83/README.md

from immutables.

For more information about ordered mappings look at https://okvs.dev

from immutables.