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

Incorrect results when using some combinations of `take`, `drop` and `slice` #3

Closed zyla closed 4 years ago

zyla commented 6 years ago

Hello. I discovered some cases where the library returns results I believe are incorrect:

GHCi, version 8.2.2: http://www.haskell.org/ghc/  :? for help
λ> import qualified Data.Vector.Persistent as PV
λ> import qualified Data.Foldable as F
λ> F.toList $ PV.slice 1 1 $ PV.drop 32 $ PV.fromList [0..33]
[32,33]

In this example we request a slice of length 1, but get back a result of length 2.

λ> F.toList $ PV.drop 1 $ PV.take 2 $ PV.fromList [0..32]
[]

Here the result should be [1].

λ> F.toList $ PV.drop 33 $ PV.drop 15 $ PV.fromList [0..33]
[33]

The first drop (first in evaluation order; the one with argument 15) seems to be completely ignored here. The number 15 can be changed to any number between 1 and 31 and gives the same result.

These test cases are minimized from larger ones which I generated using QuickCheck.

treeowl commented 4 years ago

Totally incorrect. The situation for traverse is just as bad. If I swap out the Foldable instance with one defined foldMap = foldMapDefault, I get a totally different (still totally wrong) result: [33,32,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31].

treeowl commented 4 years ago

Oh dear... chewing away with null, drop 1, and unsafeIndex goofs this up too. The whole slicing machine seems to be broken.

treeowl commented 4 years ago

@travitch, if you can document the datatypes a bit better, I can take a shot at fixing this. Such broken behavior really blocks up my ideas for improving performance.

travitch commented 4 years ago

It may be better to just tear out the slicing code and deal with the bad performance of those operations until the core is in a more usable state. I can try to remember what the slicing was attempting to do - presumably there is just some index confusion, but the traversal is so entangled with that code that it is difficult to tease them apart.

treeowl commented 4 years ago

Okay. I'll give that a shot. Best to start with something correct and try fixing performance afterwards.

treeowl commented 4 years ago

@travitch, I'll strip that, and then I'll remove the Empty constructor. That'll give us vectors as records, so we can reasonably build sliced vectors on top and get everything to unpack nicely. If we're careful, we can probably keep code duplication to a minimum.

travitch commented 4 years ago

Thanks for taking a look at this! I've been wanting to get back to this structure for a while. The performance profile is a bit weird but I have high hopes for it in some cases.