enrich the .Mutable module apis in Vector

[cartazio]

they're pretty poor in what they allow you to currently do. I thought i had a long standing ticket about this, but i cant seem to find it at the moment

@andrewthad @treeowl if you could bring some of the lovely energy to bear on the mutable subsystem of Vector, theres a HUGE amount of ways we can experiment with improving things there, and that in turn can help motivate/justify ways to evolve primitive.

i've a lot of thoughts on this direction, but seldom the bandwidth to progress things as I'd like

[cartazio]

TODO: add links to the ticket discussions/ design notes around this if applicable

[andrewthad]

I'll try to get some ideas jotted down in the next week. I think the most difficult part is probably agreeing on an API. Since there's no stream-fusion to worry about in the mutable setting, implementing things should be straightforward.

[cartazio]

i'm more than happy to iterate on api
sometimes i'm more responsive via irc (eg #numerical-haskell on freenode) and sometime email and sometime pestering on gh, but i think improving the mutable programming UX in vector is high impact and visible to more users than similar efforts in primitive (roughly speaking :) )

[andrewthad]

Here's some random thoughts I just wanted to jot down. Definitely not a full, coherent plan (also, I've abbreviated the type signatures a little):

-- in-place, element-by-element modification
mapM :: (a -> m a) -> MVector s a -> m ()
imapM :: (Int -> a -> m a) -> MVector s a -> m ()
-- traversal
mapM_ :: (a -> m b) -> MVector s a -> m ()
imapM_ :: (Int -> a -> m b) -> MVector s a -> m ()

There's really no wiggle room in how the traversals should look. They've only got that one possible type signature. But, the in-place modifiers could look like this instead:

-- in-place, element-by-element modification
mapM :: (a -> m a) -> MVector s a -> m (MVector s a)
imapM :: (Int -> a -> m a) -> MVector s a -> m (MVector s a)

Like a bunch of other functions in Data.Vector.Mutable these would implicitly mean: don't use the original vector again. The functions take, drop, etc. imply that the argument should not be used again, although this is currently not documented. This would simply follow suit.

For the element-by-element modification functions, we have the luxury of two options. However, other functions that pass over the array do not have this luxury. Consider mutable filter:

filter :: (a -> Bool) -> MVector s a -> m (MVector s a)

Like mapM, this can be rewritten to run in-place, but it must also do slicing at the end. So, we cannot write this to return unit like we could with mapM. The only option is to return MVector (even though we know it points to the same buffer as its argument).

The presence of functions like filter, uniq, mapMaybe, etc. makes me favor the second definition of mapM for the sake of consistency. I think an API that says "please pass things around in an affine manner" (even without a way to enforce this) is going to be the most consistent and the most flexible.

[cartazio]

current thoughts: have a .Mutable.Generativechild module will have the "pure but on immutable" sibling of the mutable vector api

[konsumlamm]

I very much like the idea by @andrewthad, to add in-place map/mapM/mapM_ functions. Some more ideas (using MVector from the Data.Vector.Generic.Mutable module):

• Versions of existing functions, but with arguments that operate in the given PrimMonad, for example:

  -- | Like 'modify', but with a monadic function.
  modifyM :: (PrimMonad m, MVector v a) => v (PrimState m) a -> (a -> m a) -> Int -> m ()

• In-place reverse

  -- | Reverse the vector in place.
  reverse :: (PrimMonad m, MVector v a) => v (PrimState m) a -> m ()

• previousPermutation, to complement nextPermutation

  -- | Compute the previous (lexicographically) permutation of given vector in-place.
  -- Returns False when input is the first permutation.
  previousPermutation :: (PrimMonad m, Ord e, MVector v e) => v (PrimState m) e -> m Bool

EDIT: added previousPermutation

[Bodigrim]

The functions take, drop, etc. imply that the argument should not be used again, although this is currently not documented.

I would not say so. Documentation hints (by saying "without copying it") that slices are just a different view, but as long as you keep in mind that views are linked, it is perfectly valid to modify both input and output of slice; vector-algorithms do it all the time. This is not like unsafeThaw.

That said, I'd prefer mapM :: (a -> m a) -> MVector s a -> m () to mapM :: (a -> m a) -> MVector s a -> m (MVector s a).

In-place reverse

Side note: I use mreverse for O(1) reversal of mutable vectors.

[Shimuuar]

Closed in favor of #334