Persistent Sequence

[mingmingrr]

Here's a sequence type implemented with FingerTrees.

I didn't like how PVector was structured so I moved everything into its own submodule. That way the C implementation can import the base class and "inherit" its docstrings. I could merge them into a single file like _pvector.py, or create a separate PR to copy these changes to PVector.

Other implementation differences from PVector:

• there's a few extra methods (view, splitat, chunksof) to take advantage of fast splitting
• mset can take 2-tuples instead of pairs of args
• comparison functions use iterator comparison instead of converting to list
• viewleft/viewright instead of popleft/pop, since pop has different behavior in evolvers
• evolvers implement a full MutableSequence API, and are drop-in replacements for lists and non-bounded deques

Not implemented:

• CheckedPSequence
• readme changes
• haven't tested generating docs

Some benchmarks:

Code: https://gist.github.com/mingmingrr/e9e9245b28672c824a8b492002d0780c Axes are logarithmic. X axis is container size, Y axis is time in seconds. Construction:  Get first element:  Get middle element:  Get last element:  Slice continguous chunk:  Slice with step:  Insert first element:  Insert middle element:  Insert last element:  Delete first element:  Delete middle element:  Delete last element (couldn't find a `pvector.pop()`):  Extend:  `__mul__` (psequence also takes `O(log(n)log(k))` memory): 

[tobgu]

Hi!

Thanks, this is quite a mouthful. Several thousand lines of code that I won't be able to review in great detail. And that I really don't feel like taking responsibility for in terms of bug fixing, etc.

I can see the benchmarks provided in the PR and the data structure does indeed have some appealing characteristics for certain use cases. What were the main motivations for you to create it? If this was merged would you be willing to take on the ownership to fix any issues in the sequence implementation?

An option to merging all this into pyrsistent could be to release it as its own library and have pyrsistent depend on it with a thin wrapper or similar. Did you consider that?

[mingmingrr]

I'd be willing to maintain anything related to psequence. Haven't thought of releasing it as its own library but that seems like a decent option. I would have to copy class custom_build_ext from setup.py, and pyrsistent can import psequence, PSequence, and sq. If that's your preference then I'll close this PR and move this into a new library, otherwise I'd be okay with being a maintainer.

As far as motivations, I wanted something similar to Haskell's Data.Seq with faster merge and split, which, as far as I know, doesn't currently exist in Python.

[tobgu]

Thanks, I think trying it out as a separate library that is imported is a first good step!

[mingmingrr]

Just an update, this is now published on pypi: https://pypi.org/project/pyrsistent-extras

[tobgu]

Cool! I've added a reference to your repo in the README.