Generic.takeWhile is not copy-free
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
- Issue type
- Bug
- Clarity
- Needs clarification
- Activity status
- Stale
- Tech stack
- haskell
- Domain
- performance
Research direction
Start with Data.Vector.Generic.hs and the takeWhile implementation, then compare the copy-free change for dropWhile in PR #327 and the related issues #182 and #327. Determine whether the project wants an implementation change or a documentation correction; done means the contract and behavior agree while required stream fusion is preserved.
Written by the indexing model from the issue text.
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 says:
O(n) Yield the longest prefix of elements satisfying the predicate without copying.
However, the function's implementation is:
takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
{-# INLINE takeWhile #-}
takeWhile f = unstream . Bundle.takeWhile f . stream
(See it on Hackage, or on GitHub)
The document says the function is copy-free, but it is obvious from the code that it requires copy when:
- it is used against a vector actually living in the heap, and
- the produced vector can't fuse away (for example, it is used more than once).
Note that Data.Vector.Generic.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 unstreamed 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)
- Dominant language
- Haskell
- Stars
- 401
- Forks
- 145
- PR merge metrics
- No merged PRs in 30d
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from haskell/vector
-
Difficulty 1/5 Under an hour Newbie friendliness 68/100
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
-
Difficulty 3/5 1-2 days Newbie friendliness 55/100
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
-
Difficulty 4/5 3-5 days Newbie friendliness 35/100
Similar issues
-
documentation
Difficulty 2/5 1-3 hours Newbie friendliness 65/100
-
enhancement tricorder
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
-
zip-archive-0.5 Open
Difficulty 2/5 1-3 hours Newbie friendliness 65/100
commercialhaskell/stackage#8124 · 1 comment ·
-
chore
Difficulty 1/5 Under an hour Newbie friendliness 91/100
alunduil/alunduil-chezmoi#792 ·