Generic.takeWhile is not copy-free
- Dominant language
- Haskell
- Stars
- 400
- Forks
- 145
- PR merge metrics
- No merged PRs in 30d
Description
This issue is closely related to #182, but it is a contract failure, so I guess we need to do something about this.
The description of this issue is simple: the document of the function [`Data.Vector.Generic.takeWhile`](https://hackage.haskell.org/package/vector-0.12.1.2/docs/Data-Vector-Generic.html#v:takeWhile) says:
> O(n) Yield the longest prefix of elements satisfying the predicate without copying.
However, the function's implementation is:
```Haskell
takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
{-# INLINE takeWhile #-}
takeWhile f = unstream . Bundle.takeWhile f . stream
```
(See it on [Hackage](https://hackage.haskell.org/package/vector-0.12.1.2/docs/src/Data.Vector.Generic.html#takeWhile), or on [GitHub](https://github.com/haskell/vector/blob/9de90486603193cadd7048b34f3cac55d01d4f42/Data/Vector/Generic.hs#L1377))
The document says the function is copy-free, but it is obvious from the code that it requires copy when:
1. it is used against a vector actually living in the heap, and
2. the produced vector can't fuse away (for example, it is used more than once).
Note that [`Data.Vector.Generic.dropWhile`](https://hackage.haskell.org/package/vector-0.12.1.2/docs/Data-Vector-Generic.html#v:dropWhile) also had this problem, and that we resolved it on PR #327 by making `dropWhile` actually copy-free.
On PR #327, we made it possible by letting `dropWhile` be fusible only in the case the argument vector to the function is already an `unstream`ed stream.
An obvious solution to this problem is to remove the phrase "without copying" from the documentation. It is completely sensible to choose that way.
The problem is more complex than that of `dropWhile`, and we cannot utilize the method same as the one used in #327.
I guess I've come up with a solution that makes `takeWhile` copy-free while preserving all required stream fusion, but it is rather global and complicated, and might let bugs sneak in.
I'm being lazy and I couldn't write up everything at once. I'll explain the difficulty of this problem and the proposed solution making `takeWhile` copy-free in subsequent comments.
See Also: #182 #327(+#141)
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.