Feat: add `prevPermutation`, `nextPermutationBy` and a version of `nextPermutation` that goes back to the first perm?

Start by reading Data.Vector.Generic.Mutable and the permutation changes referenced as completed in #498. Review the existing nextPermutation and nextPermutationBy API and the proposed primed variants, then check the issue discussion for naming concerns. Done means a maintainer-approved decision on whether the remaining variants belong in the public API and what they should be called.

When I was authoring #498, I noticed that there is no implementation of prevPermutation or nextPermutationBy. I also got surprised that nextPermutation, unlike in C++, does not go back to the first permutation when the argument holds the last permutation (I understand the reason for the decision, though). What do you think of adding the functions below? I'm not sure especially about the prime versions of the functions, but it doesn't hurt to record the idea, anyway.

Update: In #498, we have added (next|prev)Permutation(By)?. The only remaining task is to decide whether we should add the primed versions (next|prev)Permutation(By)?' and devise a better naming convention instead of using primes.

module Data.Vector.Generic.Mutable where

-- | Compute the (lexicographically) next permutation of the given vector in-place.
-- Returns False when the input is the last permutation; in this case the vector
-- will be updated to the first permutation, as aligned with the behavior of the C++ function 
-- @std::next_permutation@.
nextPermutation' :: (PrimMonad m, Ord e, MVector v e) => v (PrimState m) e -> m Bool

nextPermutationBy' :: (PrimMonad m, MVector v e) => (e -> e -> Ordering) -> v (PrimState m) e -> m Bool
prevPermutation' :: (PrimMonad m, Ord e, MVector v e) => v (PrimState m) e -> m Bool
prevPermutationBy' :: (PrimMonad m, MVector v e) => (e -> e -> Ordering) -> v (PrimState m) e -> m Bool

-- DONE in #498
-- nextPermutationBy :: (PrimMonad m, MVector v e) => (e -> e -> Ordering) -> v (PrimState m) e -> m Bool
-- prevPermutation :: (PrimMonad m, Ord e, MVector v e) => v (PrimState m) e -> m Bool
-- prevPermutationBy :: (PrimMonad m, MVector v e) => (e -> e -> Ordering) -> v (PrimState m) e -> m Bool

Note: the implementation can be done in one function:

nextPermutationByLtUtil :: (PrimMonad m, MVector v e) => Bool -> (e -> e -> Bool) -> v (PrimState m) e -> m Bool
nextPermutationByLtUtil always lt v
   | dim < 2 = return False
   | otherwise = stToPrim $ do
       !vlast <- unsafeRead v (dim - 1)
       !k <- decrLoop (dim - 1) vlast
       when (always || k > 0) $ reverse $ unsafeSlice k (dim - k) v
       return $ k > 0
   where
     dim = length v
     -- find the largest index k such that a[k] < a[k + 1], and then pass to the rest.
     decrLoop !i1 !vi1 | i1 > 0 = do
       let !i = i1 - 1
       !vi <- unsafeRead v i
       if vi `lt` vi1 then i1 <$ swapLoop i vi i1 vi1 dim else decrLoop i vi
     decrLoop _ !_ = return 0
     -- find the largest index l greater than k such that a[k] < a[l], and swap a[k] and a[l].
     swapLoop !k !vk = go
       where
         -- binary search.
         go !l !vl !r | r - l <= 1 = do
           -- Done; do the rest of the algorithm.
           unsafeWrite v k vl
           unsafeWrite v l vk
         go !l !vl !r = do
           !vmid <- unsafeRead v mid
           if vk `lt` vmid
             then go mid vmid r
             else go l vl mid
           where
             !mid = l + (r - l) `shiftR` 1

nextPermutation = nextPermutationByLtUtil False (<)
nextPermutation' = nextPermutationByLtUtil True (<)
nextPermutationBy cmp = nextPermutationByLtUtil False (\x y -> cmp x y == LT)
nextPermutationBy' cmp = nextPermutationByLtUtil True (\x y -> cmp x y == LT)
prevPermutation = nextPermutationByLtUtil False (>)
prevPermutation' = nextPermutationByLtUtil True (>)
prevPermutationBy cmp = nextPermutationByLtUtil False (\x y -> cmp x y == GT)
prevPermutationBy' cmp = nextPermutationByLtUtil True (\x y -> cmp x y == GT)