search

haskell / vector

An efficient implementation of Int-indexed arrays (both mutable and immutable), with a powerful loop optimisation framework .
Other
360 stars 141 forks source link

basicOverlaps is pretty weak #88

Open ekmett opened 9 years ago

ekmett commented 9 years ago

The current basicOverlaps check doesn't actually fully determine if each of the constituent sub-arrays overlap.

e.g.

  basicOverlaps (MV_3 n_1 as1 bs1 cs1) (MV_3 n_2 as2 bs2 cs2)
      = M.basicOverlaps as1 as2
        || M.basicOverlaps bs1 bs2
        || M.basicOverlaps cs1 cs2

only checks the overlap between corresponding elements, but if you used something like

roll (MV_3 n as bs cs) = MV_3 n bs cs as

then something like overlaps mv (roll mv) will report False even though it has arrays that 'overlap' the originals rendering destructive changes hazardous.

I'm not really sure that this is such a damning failing, none of the existing combinators will produce such a rotation, but I figured it was worth capturing in an issue rather than passively ignoring the concern.

An example of where it might matter would be if you let zip for unboxed vectors try to get clever about reusing the source vectors.

cartazio commented 8 years ago

this is a good idea, though as you rightly say, its not clear what the right strength should be..