haskell / haskell/vector

Generic.takeWhile is not copy-free

Open
#330 16 comments 0 reactions 0 assignees View on GitHub
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.