Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

Generic.takeWhile is not copy-free

Aperta
#330 16 commenti 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
25/100
Tipo di issue
Bug
Chiarezza
Da chiarire
Stato di attività
Ferma
Stack tecnologico
haskell
Ambito
performance

Direzione di ricerca

Inizia da Data.Vector.Generic.hs e dall’implementazione di takeWhile, quindi confronta la modifica senza copie per dropWhile in PR #327 e le issue correlate #182 e #327. Determina se il progetto richiede una modifica dell’implementazione o una correzione della documentazione; il lavoro è concluso quando il contratto e il comportamento corrispondono, preservando la stream fusion richiesta.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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:

  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 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)

Lingua principale
Haskell
Stelle
401
Fork
145
Nessuna PR unita negli ultimi 30g

Guida per i contributori

Nessuna guida per i contributori indicizzata per questo repository

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di haskell/vector

Tutte le issue di haskell/vector

Issue simili

Altre issue su Haskell

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.