haskell / haskell/containers

Add // for Data.Sequence

Open
#262 2 comments 0 reactions 0 assignees View on GitHub
feature-request Seq
Dominant language
Haskell
Stars
355
Forks
194
Avg merge
3d 4h
Merged PRs (30d)
4

Description

[Alan](http://stackoverflow.com/users/2913864/alan) has suggested [on StackOverflow](http://stackoverflow.com/questions/37505725/standard-queue-package-for-haskell/37506254?noredirect=1#comment62521038_37506254) that we add a `//` operator to `Data.Sequence` corresponding to the one in `Data.Array`. I believe that doing this efficiently likely requires access to `Data.IntMap`. We don't have that in `Data.Sequence` right now, but I'm hoping maybe the restructuring expected for the next major version after the upcoming one will allow us to do this.
### Implementation sketch

Collect all requested changes into an `IntMap`, then use something similar to `Data.Sequence.splitMap` with `Data.IntMap.split` to spread them through the tree. `splitMap` itself is overkill, because we'll likely be able to preserve whole subtrees. We may need to add some more splitting functions to `Data.IntMap`, if it supports them, but we probably want to do so anyway to match up with `Data.Map`.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.