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

Inizia leggendo Data.Vector.Generic.Mutable e le modifiche alle permutazioni indicate come completate in #498. Esamina l’API esistente di nextPermutation e nextPermutationBy e le varianti primed proposte, quindi controlla la discussione dell’issue per le questioni relative alla nomenclatura. Il lavoro è completato quando esiste una decisione approvata da un maintainer sul fatto che le varianti rimanenti debbano appartenere all’API pubblica e su come debbano essere chiamate.

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)