Add push and pull versions of vectors of known length
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 30/100
Research direction
Start by reading the linked Dupable instance in src/Data/Unrestricted/Linear.hs and the discussion of known-length vectors in issue #207. Trace how dupV and the applicative instance currently allocate, then determine the pull/push array and destination interfaces needed. Done means the requested pull-array dup method, dupV relationship, and applicative migration are implemented without repeated allocations.
Written by the indexing model from the issue text.
Description
Is your feature request related to a problem? Please describe.
Vectors of known length (or whatever they will eventually be called #207 ) have a data applicative instance. Said instance is used, for instance, in the definition of deep-copy style instances for the Dupable type class (see e.g. the instance for lists).
The limitation of these instances is that when chaining, say, f <$> dupV <*> dupV <*> dupV, each operators allocates an array. In this case, there are three allocation, but we need only one.
It is wasteful
Describe the solution you'd like
We'd like to provide a push and pull array framework (and, presumably, destinations as well) for vectors of known length.
The pull array variant would have a data applicative instance.
A new dup-type method would be added to the Dupable type class, similar to dupV but for pull arrays. And dupV would receive a default implementation in terms of the pull-array dup. The applicative-style instances would be migrated to the pull-array dup
Describe alternatives you've considered
- We could remove
dupVas a method fromDupablealtogether. Though, when creating a basic type instance (say, for thePooltype, as an example of something which isn'tMovable(Movablething will have a natural pull-array implementation)), the pull-arraydupwould need to allocate an array anyway, so ifdupVis derive, it would just copy this array which is a bit silly. So I think that we should keepdupVin.- Unless there is a meaningful implementation of a pull array from
dup2, which there may be? Probably not with the current implementation of pull array, though, but maybe the problem is the implementation, not the concept.
- Unless there is a meaningful implementation of a pull array from
- We could rely of array fusion instead. It's not really in the spirit of linear base, though. And it doesn't chain: if I have a
dupVthat calls anotherdupV, probably fusion could make both single allocation, but the latterdupVwill probably still need to allocate (unless the proper inlining happens), but it shouldn't have to. Last, but not least: the calls toUnsafe.linearwill block vector's fusion framework at least until the thorny question of multiplicity casts is solved. So it would probably be more work to build a fusion framework than to do the pull/push array story.
Additional context
N/A
- Dominant language
- Haskell
- Stars
- 359
- Forks
- 45
- PR merge metrics
- No merged PRs in 30d
Contributor guide
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 tweag/linear-base
-
Introduce basic & (additive conjunction) and possibly ⊤ (top - additive conjunctive unit) types Open
Difficulty 5/5 Over a week Newbie friendliness 35/100
tweag/linear-base#514 · 5 comments ·
-
Difficulty 3/5 1-2 days Newbie friendliness 35/100
tweag/linear-base#489 · 1 comment ·
-
type: feature request
Difficulty 4/5 3-5 days Newbie friendliness 25/100
tweag/linear-base#456 · 6 comments ·
-
type: feature request
Difficulty 5/5 Over a week Newbie friendliness 25/100
tweag/linear-base#455 · 2 comments ·
-
type: feature request
Difficulty 5/5 Over a week Newbie friendliness 25/100
tweag/linear-base#454 · 5 comments ·
All issues in tweag/linear-base
Similar issues
-
time-manager-0.4.0 Openfailure: bounds
Difficulty 1/5 Under an hour Newbie friendliness 72/100
commercialhaskell/stackage#8122 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
simplex-chat/simplex-chat#7547 ·
-
chore
Difficulty 1/5 Under an hour Newbie friendliness 90/100
alunduil/alunduil-chezmoi#775 ·
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
objectionary/phino#1350 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 68/100