search

travitch / persistent-vector

Persistent vectors for Haskell based on array mapped tries
BSD 3-Clause "New" or "Revised" License
27 stars 4 forks source link

Tr/remove slicing #13

Closed travitch closed 4 years ago

travitch commented 4 years ago

@treeowl This is a more direct take on #8. I ripped out the slicing from the latest version of master, which makes things a bit easier to understand. I kept API compatibility by adding inefficient (linear) versions of the operations formerly based on the slicing infrastructure. What do you think about redoing #10 on this?

treeowl commented 4 years ago

It's going to be an awful lot of work for me to go through and add the other improvements from #8 on top of this, but you're more than welcome to try....

Side note: Since GHC version ⟨years ago⟩, -funbox-small-strict-fields has been enabled by default with -O, so there's no need to explicitly UNPACK things like Int and Array. Only things that are more than one word need an explicit pragma now.

treeowl commented 4 years ago

TBH, I think a better bet might be to squash #8 to its base, rebase it as one commit onto master, and then maybe break it up into separate logical commits by hand if you insist.

travitch commented 4 years ago

What else was in #8? I couldn't tell

treeowl commented 4 years ago

I'll try to figure out out this weekend.

travitch commented 4 years ago

I can port the changes if you can just point out what other changes were in that PR

treeowl commented 4 years ago

There was some "by the way" stuff because I'm not disciplined about that. The only ones I remember off the top of my head were splitting unsafeIndex into a few different functions and removing some unnecessary reverse calls, but I think there were probably more. Going by my memory is not going to be

treeowl commented 4 years ago

Would you like to finish this, or shall I?

travitch commented 4 years ago

I'll take care of it in the next few days - there is no rush. I think your time is more valuable on the other issues

treeowl commented 4 years ago

I'll try.... #12 is going to take a lot of trial and error! I've started working on getting rid of that array directly in the root, and I have a decent idea of the next step, but this is almost certain to be the sort of code I need to write several times before I get something usable.

treeowl commented 4 years ago

take can surely do this: find the smallest subtree containing the desired segment, and then prune that to get the desired result. Intuitively, that should get a lot of sharing, but I haven't worked out the details. We can work it out after unsnoc.