Closed
Open
Clarified that `Data.Vector.*.Mutable.nextPermutation` does not update the vector when the original state is the last permutation.
This implements some optimization of `nextPermutation` from `Data.Vector.Generic.Mutable`. The main content of this re-implementation is the following two points: 1. Wrapping the whole implementation in `stToPrim`. This allows the compiler to optimize the code better. 2. When finding the rightmost increasing pair v[k]<v[k+1], we now search from the right, instead of from the left. This allows us to abort the search as soon as we find such a pair, giving average-case constant performance, instead of best-case linear in the previous implementation.
This adds the following three companions to the already existing `Data.Vector.*.Mutable.nextPermutation`: - `Data.Vector.*.Mutable.nextPermutationBy` - `Data.Vector.*.Mutable.prevPermutation` - `Data.Vector.*.Mutable.prevPermutationBy` They are all implemented in terms of the already existing `Data.Vector.Generic.Mutable.nextPermutationLt`.
The function `Data.Vector.Generic.Mutable.nextPermutationByLt` is
the unified implementation for the family of functions
`Data.Vector.*.Mutable.{next,prev}Permutation{,By}`.
By adding INLINE pragma to it, we may expect the some performance gain
from specialization.
Optimize Data.Vector.Generic.Mutable.nextPermutation
Optimize Mutable.nextPermutation and add {next/prev}permutation(By)
This adds the following three tests for the pair of functions
`Data.Vector.*.Mutable.{next/prev}Permutation` in
`vector/tests/Tests/Move.hs`:
1. `testRevPermutations`: For n=1,..,7, repeatedly applying
`prevPermutation` to a vector `[n,n-1..1]` produces all n! permutations
of the vector in reverse order, and applying the function to the
lexicographically smallest permutation doesn't change the vector.
2. `testNPPermutationsIsId`: Applying `nextPermutation` followed by
`prevPermutation` to a vector produces the original vector.
Note that this function uses modified versions of `nextPermutation`
and `prevPermutation` that reverse the vector if the original function
returns `False`, rendering those two functions bijective.
3. `testPNPermutationsIsId`: Applying `prevPermutation` followed by
`nextPermutation` to a vector produces the original vector. The same
caveat as above applies here.
This adds a changelog entry and `@since` annotations for: - Optimization of `Data.Vector.Generic.Mutable.nextPermutation` - Addition of `Data.Vector.Generic.Mutable.prevPermutation(By)` - Addition of `Data.Vector.Generic.Mutable.nextPermutationBy` This also tweaks the haddock comments of the functions for `Data.Vector.*.Mutable.(next|prev)Permutation(By)?` for a better readability.
Implement benchmarks to test performance of nextPermutation and prevPermutation on mutable vectors. Tests include: - Looping through all permutations on small vectors - Applying bijective versions n times on: - Ascending permutations of size n - Descending permutations of size n - Random permutations of size n - For a baseline, copying a vector of size n once. Benchmarks for bijective permutations begins with such a copy, and you might want to remove the impact of copying from the results. Benchmarks cover both forward (next) and reverse (prev) operations.
netbsd-srcmastr pushed a commit to NetBSD/pkgsrc that referenced this pull request
Jan 29, 2025
# Changes in version 0.13.2.0 * Strict boxed vector `Data.Vector.Strict` and `Data.Vector.Strict.Mutable` is added (#488). it ensures that all values in the vector are evaluated to WHNF. * `DoNotUnboxStrict`, `DoNotUnboxLazy`, and `DoNotUnboxNormalForm` wrapper are added for defining unbox instances for types that contain not unboxable fields. [#503](haskell/vector#506), [#508](haskell/vector#508) * `spanR` and `breakR` were added [#476](haskell/vector#476). They allow parsing vector from the right. * We had some improvements on `*.Mutable.{next,prev}Permutation{,By}` [#498](haskell/vector#498): * Add `*.Mutable.prevPermutation{,By}` and `*.Mutable.nextPermutationBy` * Improve time performance. We may now expect good specialization supported by inlining. The implementation has also been algorithmically updated: in the previous implementation the full enumeration of all the permutations of `[1..n]` took Omega(n*n!), but it now takes O(n!). * Add tests for `{next,prev}Permutation` * Add benchmarks for `{next,prev}Permutation` * Cabal >= 3.0 is now required for building package (#481). * `vector:benchmarks-O2` public sublibrary containing benchmarks is added (#481). * Type family `Mutable` provides instances for arrays from `primitive`. * Various documentation improvements.
msk pushed a commit to msk/pkgsrc that referenced this pull request
May 11, 2026
# Changes in version 0.13.2.0 * Strict boxed vector `Data.Vector.Strict` and `Data.Vector.Strict.Mutable` is added (#488). it ensures that all values in the vector are evaluated to WHNF. * `DoNotUnboxStrict`, `DoNotUnboxLazy`, and `DoNotUnboxNormalForm` wrapper are added for defining unbox instances for types that contain not unboxable fields. [#503](haskell/vector#506), [#508](haskell/vector#508) * `spanR` and `breakR` were added [#476](haskell/vector#476). They allow parsing vector from the right. * We had some improvements on `*.Mutable.{next,prev}Permutation{,By}` [#498](haskell/vector#498): * Add `*.Mutable.prevPermutation{,By}` and `*.Mutable.nextPermutationBy` * Improve time performance. We may now expect good specialization supported by inlining. The implementation has also been algorithmically updated: in the previous implementation the full enumeration of all the permutations of `[1..n]` took Omega(n*n!), but it now takes O(n!). * Add tests for `{next,prev}Permutation` * Add benchmarks for `{next,prev}Permutation` * Cabal >= 3.0 is now required for building package (#481). * `vector:benchmarks-O2` public sublibrary containing benchmarks is added (#481). * Type family `Mutable` provides instances for arrays from `primitive`. * Various documentation improvements.
jperkin pushed a commit to TritonDataCenter/pkgsrc that referenced this pull request
May 14, 2026
# Changes in version 0.13.2.0 * Strict boxed vector `Data.Vector.Strict` and `Data.Vector.Strict.Mutable` is added (#488). it ensures that all values in the vector are evaluated to WHNF. * `DoNotUnboxStrict`, `DoNotUnboxLazy`, and `DoNotUnboxNormalForm` wrapper are added for defining unbox instances for types that contain not unboxable fields. [#503](haskell/vector#506), [#508](haskell/vector#508) * `spanR` and `breakR` were added [#476](haskell/vector#476). They allow parsing vector from the right. * We had some improvements on `*.Mutable.{next,prev}Permutation{,By}` [#498](haskell/vector#498): * Add `*.Mutable.prevPermutation{,By}` and `*.Mutable.nextPermutationBy` * Improve time performance. We may now expect good specialization supported by inlining. The implementation has also been algorithmically updated: in the previous implementation the full enumeration of all the permutations of `[1..n]` took Omega(n*n!), but it now takes O(n!). * Add tests for `{next,prev}Permutation` * Add benchmarks for `{next,prev}Permutation` * Cabal >= 3.0 is now required for building package (#481). * `vector:benchmarks-O2` public sublibrary containing benchmarks is added (#481). * Type family `Mutable` provides instances for arrays from `primitive`. * Various documentation improvements.