Any plans for a list/vector?

[jrbrodie77]

I like the trend of increasing functional programming data types for Python. Any plans for a list/vector?

[1st1]

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

[antonagestam]

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

[1st1]

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.

[amirouche]

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?

[1st1]

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.

[amirouche]

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 :love_letter:.

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

[1st1]

@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.

[kkpattern]

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.

[amirouche]

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

[amirouche]

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