haskell / haskell/vector

overlaps for Data.Vector.Mutable behaves oddly for empty vectors

Open
#444 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
400
Forks
145
PR merge metrics
No merged PRs in 30d

Description

The `basicOverlaps` implementation for Data.Vector.Mutable is:

``` haskell
basicOverlaps (MVector i m arr1) (MVector j n arr2)
= sameMutableArray arr1 arr2
&& (between i j (j+n) || between j i (i+m))
where
between x y z = x >= y && x < z
```

This will return `True` for two vectors where two vectors share the same mutable array and offset, but one has a zero length and the other has a non-zero length. I cannot find a precise definition of what it means for possibly-empty vectors to overlap, so it's hard to say for sure this is wrong, but it certainly disagrees with my understanding of what `overlaps` ought to mean.

I suggest this implementation instead:

``` haskell
basicOverlaps (MVector i m arr1) (MVector j n arr2)
= sameMutableArray arr1 arr2 && i < j + n && j < i + m
```

That will still report an overlap for an empty vector with an offset in the middle of a containing non-empty vector, though. It's even less clear what the right answer is there. So I guess what we really need is a precise specification first, and then we can write an implementation that matches it.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.