Proposal: Add // for Data.Sequence
BACKGROUND ---------- Data.Array provides (//) for incremental array updates. Data.Sequence lacks this useful functionality. SCOPE ----- Doing this efficiently may require that Data.Sequence access Data.IntMap. (It currently does not.) David Feuer commented: 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. SOLUTIONS ----------- David Feuer offered the following implementation sketch. (See https://github.com/haskell/containers/issues/262) 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. David Feuer commented: splitMap itself is overkill, because we'll likely be able to preserve whole subtrees. WHAT MIGHT BREAK ---------------- No anticipated breakage.
REQUEST ------- The request is to add `sortOn` to Data.Sequence. `sortOn f` would be equivalent to `sortBy . comparing f`, but would offer a performance advantage by using a Schwartzian transform to only evaluate `f` once for each element in the input sequence. BACKGROUND ---------- Adding `sortOn` to `Data.List` was proposed at least as early as 2008: http://www.haskell.org/pipermail/libraries/2008-October/010797.html It was added in 2014, in response to this feature request: https://ghc.haskell.org/trac/ghc/ticket/9004 RATIONALES ---------- - convenience - performance: faster than `sortBy` - safety: encourages (although does not require) reliance on existing instances of Ord - interface consistency (specifically, when comparing to Data.List) Comment: it is certainly possible to pick at each of these rationales. See the discussion here: http://stackoverflow.com/questions/37691898/why-is-sortby-so-oddly-unconstra... SCOPE ----- Introduces no new dependencies except possibly on `Data.Ord.comparing`. SOLUTIONS ----------- The implementation in Data.List is:: sortOn :: Ord b => (a -> b) -> [a] -> [a] sortOn f = map snd . sortBy (comparing fst) . map (\x -> let y = f x in y `seq` (y, x)) An analogous implementation is possible for Data.Sequence. However, this request does not propose a specific implementation. WHAT MIGHT BREAK ---------------- No anticipated breakage.
participants (1)
-
Alan Isaac