ac-library-hs 1.5.1.0 → 1.5.2.0

raw patch · 12 files changed

+407/−55 lines, 12 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +5/−0
• ac-library-hs.cabal +2/−1
• src/AtCoder/Extra/Graph.hs +2/−3
• src/AtCoder/Extra/IntMap.hs +25/−25
• src/AtCoder/Extra/Pdsu.hs +2/−1
• src/AtCoder/Extra/SegTree2d.hs +1/−1
• src/AtCoder/Extra/Seq/Map.hs +1/−1
• src/AtCoder/Extra/Tree.hs +2/−1
• src/AtCoder/Extra/Tree/Hld.hs +1/−1
• src/AtCoder/Extra/Vector/Prim.hs +342/−0
• src/AtCoder/MaxFlow.hs +22/−21
• test/Main.hs +2/−0

@@ -1,5 +1,10 @@ # Revision history for acl-hs +## 1.5.2.0 -- June 2025++- Added `AtCoder.Extra.Vector.Prim`+- Fixed some `INLINE` pragmas+ ## 1.5.1.0 -- June 2025  - Added `transformers` as a new dependency.

@@ -4,7 +4,7 @@ -- PVP summary:  +-+------- breaking API changes --               | | +----- non-breaking API additions --               | | | +--- code changes with no API change-version:         1.5.1.0+version:         1.5.2.0 synopsis:        Data structures and algorithms description:   Haskell port of [ac-library](https://github.com/atcoder/ac-library), a library for competitive@@ -98,6 +98,7 @@     AtCoder.Extra.Tree.Lct     AtCoder.Extra.Tree.TreeMonoid     AtCoder.Extra.Vector+    AtCoder.Extra.Vector.Prim     AtCoder.Extra.WaveletMatrix     AtCoder.Extra.WaveletMatrix.BitVector     AtCoder.Extra.WaveletMatrix.Raw

@@ -187,7 +187,6 @@ -- -- @since 1.1.0.0 {-# INLINEABLE swapDupe' #-}--- NOTE: concatMap does not fuse anyways, as the vector's code says swapDupe' :: VU.Vector (Int, Int) -> VU.Vector (Int, Int) swapDupe' uvs = VU.create $ do   vec <- VUM.unsafeNew (2 * VU.length uvs)@@ -948,7 +947,7 @@ -- deque, not distance of unreachable vertices. -- -- ==== Constraints--- - \(\marhrm{capacity} \ge 0\)+-- - \(\mathrm{capacity} \ge 0\) -- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr@@ -985,7 +984,7 @@ -- deque, not distance of unreachable vertices. -- -- ==== Constraints--- - \(\marhrm{capacity} \ge 0\)+-- - \(\mathrm{capacity} \ge 0\) -- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr

@@ -102,98 +102,98 @@ -- | \(O(n)\) Creates an `IntMap` for an interval \([0, n)\). -- -- @since 1.1.0.0-{-# INLINEABLE new #-}+{-# INLINE new #-} new :: (PrimMonad m, VU.Unbox a) => Int -> m (IntMap (PrimState m) a) new cap = stToPrim $ newST cap  -- | \(O(n + m \log n)\) Creates an `IntMap` for an interval \([0, n)\) with initial entries. -- -- @since 1.1.0.0-{-# INLINEABLE build #-}+{-# INLINE build #-} build :: (PrimMonad m, VU.Unbox a) => Int -> VU.Vector (Int, a) -> m (IntMap (PrimState m) a) build cap xs = stToPrim $ buildST cap xs  -- | \(O(1)\) Returns the capacity \(n\), where the interval \([0, n)\) is covered by the map. -- -- @since 1.1.0.0-{-# INLINEABLE capacity #-}+{-# INLINE capacity #-} capacity :: IntMap s a -> Int capacity = IS.capacity . setIM  -- | \(O(1)\) Returns the number of entries in the map. -- -- @since 1.1.0.0-{-# INLINEABLE size #-}+{-# INLINE size #-} size :: (PrimMonad m) => IntMap (PrimState m) a -> m Int size = IS.size . setIM  -- | \(O(1)\) Returns whether the map is empty. -- -- @since 1.1.0.0-{-# INLINEABLE null #-}+{-# INLINE null #-} null :: (PrimMonad m) => IntMap (PrimState m) a -> m Bool null = IS.null . setIM  -- | \(O(\log n)\) Looks up the value associated with a key. -- -- @since 1.1.0.0-{-# INLINEABLE lookup #-}+{-# INLINE lookup #-} lookup :: (PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> Int -> m (Maybe a) lookup im k = stToPrim $ lookupST im k  -- | \(O(\log n)\) Tests whether a key \(k\) is in the map. -- -- @since 1.1.0.0-{-# INLINEABLE member #-}+{-# INLINE member #-} member :: (PrimMonad m) => IntMap (PrimState m) a -> Int -> m Bool member = IS.member . setIM  -- | \(O(\log n)\) Tests whether a key \(k\) is not in the map. -- -- @since 1.1.0.0-{-# INLINEABLE notMember #-}+{-# INLINE notMember #-} notMember :: (PrimMonad m) => IntMap (PrimState m) a -> Int -> m Bool notMember = IS.notMember . setIM  -- | \(O(\log n)\) Looks up the \((k, v)\) pair with the smallest key \(k\) such that \(k \ge k_0\). -- -- @since 1.1.0.0-{-# INLINEABLE lookupGE #-}+{-# INLINE lookupGE #-} lookupGE :: (PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> Int -> m (Maybe (Int, a)) lookupGE im k = stToPrim $ lookupGEST im k  -- | \(O(\log n)\) Looks up the \((k, v)\) pair with the smallest \(k\) such that \(k \gt k_0\). -- -- @since 1.1.0.0-{-# INLINEABLE lookupGT #-}+{-# INLINE lookupGT #-} lookupGT :: (PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> Int -> m (Maybe (Int, a)) lookupGT is k = stToPrim $ lookupGEST is (k + 1)  -- | \(O(\log n)\) Looks up the \((k, v)\) pair with the largest key \(k\) such that \(k \le k_0\). -- -- @since 1.1.0.0-{-# INLINEABLE lookupLE #-}+{-# INLINE lookupLE #-} lookupLE :: (HasCallStack, PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> Int -> m (Maybe (Int, a)) lookupLE im k = stToPrim $ lookupLEST im k  -- | \(O(\log n)\) Looks up the \((k, v)\) pair with the largest key \(k\) such that \(k \lt k_0\). -- -- @since 1.1.0.0-{-# INLINEABLE lookupLT #-}+{-# INLINE lookupLT #-} lookupLT :: (PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> Int -> m (Maybe (Int, a)) lookupLT im k = stToPrim $ lookupLEST im (k - 1)  -- | \(O(\log n)\) Looks up the \((k, v)\) pair with the minimum key \(k\). -- -- @since 1.1.0.0-{-# INLINEABLE lookupMin #-}+{-# INLINE lookupMin #-} lookupMin :: (PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> m (Maybe (Int, a)) lookupMin im = stToPrim $ lookupMinST im  -- | \(O(\log n)\) Looks up the \((k, v)\) pair with the maximum key \(k\). -- -- @since 1.1.0.0-{-# INLINEABLE lookupMax #-}+{-# INLINE lookupMax #-} lookupMax :: (PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> m (Maybe (Int, a)) lookupMax im = stToPrim $ lookupMaxST im @@ -201,7 +201,7 @@ -- exists, it is overwritten. -- -- @since 1.1.0.0-{-# INLINEABLE insert #-}+{-# INLINE insert #-} insert :: (HasCallStack, PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> Int -> a -> m () insert im k v = stToPrim $ insertST im k v @@ -209,7 +209,7 @@ -- exists, it overwritten with \(f(v_{\mathrm{new}}, v_{\mathrm{old}})\). -- -- @since 1.1.0.0-{-# INLINEABLE insertWith #-}+{-# INLINE insertWith #-} insertWith :: (HasCallStack, PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> (a -> a -> a) -> Int -> a -> m () insertWith im f k v = stToPrim $ insertWithST im f k v @@ -217,7 +217,7 @@ -- does not exist, it does nothing. -- -- @since 1.1.0.0-{-# INLINEABLE modify #-}+{-# INLINE modify #-} modify :: (HasCallStack, PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> (a -> a) -> Int -> m () modify im f k = stToPrim $ modifyST im f k @@ -225,7 +225,7 @@ -- does not exist, it does nothing. -- -- @since 1.1.0.0-{-# INLINEABLE modifyM #-}+{-# INLINE modifyM #-} modifyM :: (HasCallStack, PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> (a -> m a) -> Int -> m () modifyM IntMap {..} f k = do   b <- IS.member setIM k@@ -236,7 +236,7 @@ -- such key exists. Returns whether the key existed. -- -- @since 1.1.0.0-{-# INLINEABLE delete #-}+{-# INLINE delete #-} delete :: (PrimMonad m) => IntMap (PrimState m) a -> Int -> m Bool delete im = stToPrim . deleteST im @@ -244,42 +244,42 @@ -- such key exists. -- -- @since 1.1.0.0-{-# INLINEABLE delete_ #-}+{-# INLINE delete_ #-} delete_ :: (PrimMonad m) => IntMap (PrimState m) a -> Int -> m () delete_ im = stToPrim . deleteST_ im  -- | \(O(\log n)\) Deletes the \((k, v)\) pair with the minimum key \(k\) in the map. -- -- @since 1.1.0.0-{-# INLINEABLE deleteMin #-}+{-# INLINE deleteMin #-} deleteMin :: (HasCallStack, PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> m (Maybe (Int, a)) deleteMin is = stToPrim $ deleteMinST is  -- | \(O(\log n)\) Deletes the \((k, v)\) pair with maximum key \(k\) in the map. -- -- @since 1.1.0.0-{-# INLINEABLE deleteMax #-}+{-# INLINE deleteMax #-} deleteMax :: (HasCallStack, PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> m (Maybe (Int, a)) deleteMax is = stToPrim $ deleteMaxST is  -- | \(O(n \log n)\) Enumerates the keys in the map. -- -- @since 1.1.0.0-{-# INLINEABLE keys #-}+{-# INLINE keys #-} keys :: (PrimMonad m) => IntMap (PrimState m) a -> m (VU.Vector Int) keys = stToPrim . keysST  -- | \(O(n \log n)\) Enumerates the elements (values) in the map. -- -- @since 1.1.0.0-{-# INLINEABLE elems #-}+{-# INLINE elems #-} elems :: (PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> m (VU.Vector a) elems = stToPrim . elemsST  -- | \(O(n \log n)\) Enumerates the key-value pairs in the map. -- -- @since 1.1.0.0-{-# INLINEABLE assocs #-}+{-# INLINE assocs #-} assocs :: (PrimMonad m, VU.Unbox a) => IntMap (PrimState m) a -> m (VU.Vector (Int, a)) assocs = stToPrim . assocsST 

@@ -46,6 +46,7 @@ where  import AtCoder.Internal.Assert qualified as ACIA+import AtCoder.Extra.Vector.Prim qualified as EVP import Control.Monad import Control.Monad.Primitive (PrimMonad, PrimState, stToPrim) import Control.Monad.ST (ST)@@ -369,7 +370,7 @@ groupsST :: (Semigroup a, VU.Unbox a) => Pdsu s a -> ST s (V.Vector (VU.Vector Int)) groupsST dsu@Pdsu {..} = do   groupSize <- VUM.replicate nPdsu (0 :: Int)-  leaders <- VU.generateM nPdsu $ \i -> do+  leaders <- EVP.generateM nPdsu $ \i -> do     li <- leaderST dsu i     VGM.modify groupSize (+ 1) li     pure li

@@ -126,7 +126,7 @@ -- | \(O(n \log n)\) Creates a `SegTree2d` from a vector of \((x, y)\) coordinates. -- -- @since 1.2.3.0-{-# INLINEABLE new #-}+{-# INLINE new #-} new ::   (PrimMonad m, Monoid a, VU.Unbox a) =>   -- | \((x, y)\) vector

@@ -144,7 +144,7 @@ -- performance. -- -- @since 1.2.1.0-{-# INLINEABLE new #-}+{-# INLINE new #-} new :: (PrimMonad m, Monoid f, VU.Unbox f, VU.Unbox k, VU.Unbox v, Monoid v) => Int -> m (Map (PrimState m) f k v) new n = stToPrim $ do   seqMap <- Seq.new n

@@ -26,6 +26,7 @@  import AtCoder.Dsu qualified as Dsu import AtCoder.Extra.Graph qualified as Gr+import AtCoder.Extra.Vector.Prim qualified as EVP import Control.Monad (when) import Control.Monad.ST (runST) import Data.Bit (Bit (..))@@ -165,7 +166,7 @@         (VU.replicate (VU.length edges) (Bit False))         <$>       )-      . VU.mapM+      . EVP.mapM         ( \(i :: Int) -> do             let !u = us VG.! i             let !v = vs VG.! i

@@ -226,7 +226,7 @@ --   \((v, u, w)\) edges are required). -- -- @since 1.1.0.0-{-# INLINEABLE new #-}+{-# INLINE new #-} new :: forall w. (HasCallStack) => Gr.Csr w -> Hld new tree = newAt tree 0 

@@ -0,0 +1,342 @@+-- | Monadic vector functions with @PrimMonad m@ constraints. They can fuse well.+--+-- Related issue: https://www.github.com/haskell/vector/issues/416.+--+-- Note that these functions are not 100% guaranteed to be sound.+--+-- @since 1.5.2.0+module AtCoder.Extra.Vector.Prim+  ( -- * Construction++    -- ** Monadic initialization+    replicateM,+    generateM,+    iterateNM,++    -- ** Unfolding+    constructNM,+    constructrNM,++    -- * Elementwise operations++    -- ** Monadic mapping+    mapM,+    mapM_,+    imapM,+    imapM_,+    forM,+    forM_,+    iforM,+    iforM_,++    -- ** Monadic zipping+    zipWithM,+    zipWithM_,+    izipWithM,+    izipWithM_,++    -- * Concat map+    concatMapM,+    iconcatMapM,++    -- * Working with predicates++    -- ** Filtering+    filterM,+    mapMaybeM,+    imapMaybeM,++    -- ** Monadic scanl+    prescanlM,+    prescanlM',+    postscanlM,+    postscanlM',+    scanlM,+    scanlM',+    scanl1M,+    scanl1M',+  )+where++import Control.Monad.Primitive (PrimMonad)+import Data.Vector.Fusion.Bundle qualified as Bundle+import Data.Vector.Fusion.Bundle.Monadic qualified as BundleM+import Data.Vector.Generic qualified as VG+import Data.Vector.Generic.Mutable qualified as VGM+import GHC.Stack (HasCallStack)+import Prelude hiding (mapM, mapM_)++-- | ==== Constraints+-- - \(n \ge 0\)+--+-- @since 1.5.2.0+{-# INLINE replicateM #-}+replicateM :: (PrimMonad m, VG.Vector v a) => Int -> m a -> m (v a)+replicateM n f = unstreamPrimM (BundleM.replicateM n f)++-- | ==== Constraints+-- - \(n \ge 0\)+--+-- @since 1.5.2.0+{-# INLINE generateM #-}+generateM :: (PrimMonad m, VG.Vector v a) => Int -> (Int -> m a) -> m (v a)+generateM n f = unstreamPrimM (BundleM.generateM n f)++-- | ==== Constraints+-- - \(n \ge 0\)+--+-- @since 1.5.2.0+{-# INLINE iterateNM #-}+iterateNM :: (PrimMonad m, VG.Vector v a) => Int -> (a -> m a) -> a -> m (v a)+iterateNM n f x = unstreamPrimM (BundleM.iterateNM n f x)++-- | ==== Constraints+-- - \(n \ge 0\)+--+-- @since 1.5.2.0+{-# INLINE constructNM #-}+constructNM :: forall m v a. (PrimMonad m, VG.Vector v a) => Int -> (v a -> m a) -> m (v a)+constructNM n f = do+  v <- VGM.new n+  v' <- VG.unsafeFreeze v+  fill v' 0+  where+    fill :: v a ->Int -> m (v a)+    fill !v i+      | i < n = do+          x <- f (VG.unsafeTake i v)+          VG.elemseq v x $ do+            v' <- VG.unsafeThaw v+            VGM.unsafeWrite v' i x+            v'' <- VG.unsafeFreeze v'+            fill v'' (i + 1)+    fill v _ = pure v++-- | ==== Constraints+-- - \(n \ge 0\)+--+-- @since 1.5.2.0+{-# INLINE constructrNM #-}+constructrNM :: forall m v a. (PrimMonad m, VG.Vector v a) => Int -> (v a -> m a) -> m (v a)+constructrNM n f = do+  v <- n `seq` VGM.new n+  v' <- VG.unsafeFreeze v+  fill v' 0+  where+    fill :: v a ->Int -> m (v a)+    fill !v i+      | i < n = do+          x <- f (VG.unsafeSlice (n - i) i v)+          VG.elemseq v x $ do+            v' <- VG.unsafeThaw v+            VGM.unsafeWrite v' (n - i - 1) x+            v'' <- VG.unsafeFreeze v'+            fill v'' (i + 1)+    fill v _ = pure v++-- | @since 1.5.2.0+{-# INLINE mapM #-}+mapM :: (PrimMonad m, VG.Vector v a, VG.Vector v b) => (a -> m b) -> v a -> m (v b)+mapM f = unstreamPrimM . Bundle.mapM f . VG.stream++-- | @since 1.5.2.0+{-# INLINE imapM #-}+imapM :: (PrimMonad m, VG.Vector v a, VG.Vector v b) => (Int -> a -> m b) -> v a -> m (v b)+imapM f = unstreamPrimM . Bundle.mapM (uncurry f) . Bundle.indexed . VG.stream++-- | @since 1.5.2.0+{-# INLINE mapM_ #-}+mapM_ :: (PrimMonad m, VG.Vector v a) => (a -> m b) -> v a -> m ()+mapM_ f = Bundle.mapM_ f . VG.stream++-- | @since 1.5.2.0+{-# INLINE imapM_ #-}+imapM_ :: (PrimMonad m, VG.Vector v a) => (Int -> a -> m b) -> v a -> m ()+imapM_ f = Bundle.mapM_ (uncurry f) . Bundle.indexed . VG.stream++-- | @since 1.5.2.0+{-# INLINE forM #-}+forM :: (PrimMonad m, VG.Vector v a, VG.Vector v b) => v a -> (a -> m b) -> m (v b)+forM as f = mapM f as++-- | @since 1.5.2.0+{-# INLINE forM_ #-}+forM_ :: (PrimMonad m, VG.Vector v a) => v a -> (a -> m b) -> m ()+forM_ as f = mapM_ f as++-- | @since 1.5.2.0+iforM :: (PrimMonad m, VG.Vector v a, VG.Vector v b) => v a -> (Int -> a -> m b) -> m (v b)+{-# INLINE iforM #-}+iforM as f = imapM f as++-- | @since 1.5.2.0+{-# INLINE iforM_ #-}+iforM_ :: (PrimMonad m, VG.Vector v a) => v a -> (Int -> a -> m b) -> m ()+iforM_ as f = imapM_ f as++-- | @since 1.5.2.0+{-# INLINE zipWithM #-}+zipWithM :: (PrimMonad m, VG.Vector v a, VG.Vector v b, VG.Vector v c) => (a -> b -> m c) -> v a -> v b -> m (v c)+zipWithM f = \as bs -> unstreamPrimM $ Bundle.zipWithM f (VG.stream as) (VG.stream bs)++-- | @since 1.5.2.0+{-# INLINE izipWithM #-}+izipWithM :: (PrimMonad m, VG.Vector v a, VG.Vector v b, VG.Vector v c) => (Int -> a -> b -> m c) -> v a -> v b -> m (v c)+izipWithM m as bs = unstreamPrimM . Bundle.zipWithM (uncurry m) (Bundle.indexed (VG.stream as)) $ VG.stream bs++-- | @since 1.5.2.0+{-# INLINE zipWithM_ #-}+zipWithM_ :: (PrimMonad m, VG.Vector v a, VG.Vector v b) => (a -> b -> m c) -> v a -> v b -> m ()+zipWithM_ f = \as bs -> Bundle.zipWithM_ f (VG.stream as) (VG.stream bs)++-- | @since 1.5.2.0+{-# INLINE izipWithM_ #-}+izipWithM_ :: (PrimMonad m, VG.Vector v a, VG.Vector v b) => (Int -> a -> b -> m c) -> v a -> v b -> m ()+izipWithM_ m as bs = Bundle.zipWithM_ (uncurry m) (Bundle.indexed (VG.stream as)) $ VG.stream bs++-- | Maps each element to a vector and concatenate the results.+--+-- @since 1.5.2.0+{-# INLINE concatMapM #-}+concatMapM ::+  (HasCallStack, PrimMonad m, VG.Vector v a, VG.Vector v b) =>+  (a -> m (v b)) ->+  v a ->+  m (v b)+concatMapM f =+  unstreamPrimM+    . BundleM.concatVectors+    . BundleM.mapM f+    . BundleM.fromVector++-- | Maps each element to a vector and concatenate the results.+--+-- @since 1.5.2.0+{-# INLINE iconcatMapM #-}+iconcatMapM ::+  (HasCallStack, PrimMonad m, VG.Vector v a, VG.Vector v b) =>+  (Int -> a -> m (v b)) ->+  v a ->+  m (v b)+iconcatMapM f =+  unstreamPrimM+    . BundleM.concatVectors+    . BundleM.mapM (uncurry f)+    . BundleM.indexed+    . BundleM.fromVector++-- | @since 1.5.2.0+{-# INLINE filterM #-}+filterM :: (PrimMonad m, VG.Vector v a) => (a -> m Bool) -> v a -> m (v a)+filterM f = unstreamPrimM . Bundle.filterM f . VG.stream++-- | @since 1.5.2.0+mapMaybeM :: (PrimMonad m, VG.Vector v a, VG.Vector v b) => (a -> m (Maybe b)) -> v a -> m (v b)+{-# INLINE mapMaybeM #-}+mapMaybeM f = unstreamPrimM . Bundle.mapMaybeM f . VG.stream++-- | @since 0.12.2.0+{-# INLINE imapMaybeM #-}+imapMaybeM :: (PrimMonad m, VG.Vector v a, VG.Vector v b) => (Int -> a -> m (Maybe b)) -> v a -> m (v b)+imapMaybeM f = unstreamPrimM . Bundle.mapMaybeM (\(i, a) -> f i a) . Bundle.indexed . VG.stream++-- | https://github.com/haskell/vector/issues/416+{-# INLINE [1] unstreamPrimM #-}+unstreamPrimM :: (PrimMonad m, VG.Vector v a) => BundleM.Bundle m u a -> m (v a)+unstreamPrimM s = VGM.munstream s >>= VG.unsafeFreeze++-- | @since 1.5.2.0+{-# INLINE prescanlM #-}+prescanlM :: (HasCallStack, PrimMonad m, VG.Vector v a, VG.Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)+prescanlM f x0 =+  unstreamPrimM+    . prescanlMB f x0+    . VG.stream++-- | @since 1.5.2.0+{-# INLINE prescanlM' #-}+prescanlM' :: (HasCallStack, PrimMonad m, VG.Vector v a, VG.Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)+prescanlM' f x0 =+  unstreamPrimM+    . prescanlMB' f x0+    . VG.stream++-- | @since 1.5.2.0+{-# INLINE postscanlM #-}+postscanlM :: (HasCallStack, PrimMonad m, VG.Vector v a, VG.Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)+postscanlM f x0 =+  unstreamPrimM+    . postscanlMB f x0+    . VG.stream++-- | @since 1.5.2.0+{-# INLINE postscanlM' #-}+postscanlM' :: (HasCallStack, PrimMonad m, VG.Vector v a, VG.Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)+postscanlM' f x0 =+  unstreamPrimM+    . postscanlMB' f x0+    . VG.stream++-- | @since 1.5.2.0+{-# INLINE scanlM #-}+scanlM :: (HasCallStack, PrimMonad m, VG.Vector v a, VG.Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)+scanlM f x0 =+  unstreamPrimM+    . scanlMB f x0+    . VG.stream++-- | @since 1.5.2.0+{-# INLINE scanlM' #-}+scanlM' :: (HasCallStack, PrimMonad m, VG.Vector v a, VG.Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)+scanlM' f x0 =+  unstreamPrimM+    . scanlMB' f x0+    . VG.stream++-- | @since 1.5.2.0+{-# INLINE scanl1M #-}+scanl1M :: (HasCallStack, PrimMonad m, VG.Vector v a) => (a -> a -> m a) -> v a -> m (v a)+scanl1M f =+  unstreamPrimM+    . scanl1MB f+    . VG.stream++-- | @since 1.5.2.0+{-# INLINE scanl1M' #-}+scanl1M' :: (HasCallStack, PrimMonad m, VG.Vector v a) => (a -> a -> m a) -> v a -> m (v a)+scanl1M' f =+  unstreamPrimM+    . scanl1MB' f+    . VG.stream++{-# INLINE prescanlMB #-}+prescanlMB :: (Monad m) => (a -> b -> m a) -> a -> Bundle.Bundle v b -> BundleM.Bundle m v a+prescanlMB f x0 = BundleM.prescanlM f x0 . Bundle.lift++{-# INLINE prescanlMB' #-}+prescanlMB' :: (Monad m) => (a -> b -> m a) -> a -> Bundle.Bundle v b -> BundleM.Bundle m v a+prescanlMB' f x0 = BundleM.prescanlM' f x0 . Bundle.lift++{-# INLINE postscanlMB #-}+postscanlMB :: (Monad m) => (a -> b -> m a) -> a -> Bundle.Bundle v b -> BundleM.Bundle m v a+postscanlMB f x0 = BundleM.postscanlM f x0 . Bundle.lift++{-# INLINE postscanlMB' #-}+postscanlMB' :: (Monad m) => (a -> b -> m a) -> a -> Bundle.Bundle v b -> BundleM.Bundle m v a+postscanlMB' f x0 = BundleM.postscanlM' f x0 . Bundle.lift++{-# INLINE scanlMB #-}+scanlMB :: (Monad m) => (a -> b -> m a) -> a -> Bundle.Bundle v b -> BundleM.Bundle m v a+scanlMB f x0 = BundleM.scanlM f x0 . Bundle.lift++{-# INLINE scanlMB' #-}+scanlMB' :: (Monad m) => (a -> b -> m a) -> a -> Bundle.Bundle v b -> BundleM.Bundle m v a+scanlMB' f x0 = BundleM.scanlM' f x0 . Bundle.lift++{-# INLINE scanl1MB #-}+scanl1MB :: (Monad m) => (a -> a -> m a) -> Bundle.Bundle v a -> BundleM.Bundle m v a+scanl1MB f = BundleM.scanl1M f . Bundle.lift++{-# INLINE scanl1MB' #-}+scanl1MB' :: (Monad m) => (a -> a -> m a) -> Bundle.Bundle v a -> BundleM.Bundle m v a+scanl1MB' f = BundleM.scanl1M' f . Bundle.lift

@@ -59,6 +59,7 @@  -- TODO: add `build`. +import AtCoder.Extra.Vector.Prim qualified as EVP import AtCoder.Internal.Assert qualified as ACIA import AtCoder.Internal.GrowVec qualified as ACIGV import AtCoder.Internal.Queue qualified as ACIQ@@ -292,7 +293,7 @@ -- -------------------------------------------------------------------------------------------------  {-# INLINEABLE newST #-}-newST :: (PrimMonad m, VU.Unbox cap) => Int -> m (MfGraph (PrimState m) cap)+newST :: (VU.Unbox cap) => Int -> ST s (MfGraph s cap) newST nG = do   gG <- V.replicateM nG (ACIGV.new 0)   posG <- ACIGV.new 0@@ -300,9 +301,9 @@  {-# INLINEABLE addEdgeST #-} addEdgeST ::-  (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) =>+  (HasCallStack, Num cap, Ord cap, VU.Unbox cap) =>   -- | Graph-  MfGraph (PrimState m) cap ->+  MfGraph s cap ->   -- | from   Int ->   -- | to@@ -310,7 +311,7 @@   -- | cap   cap ->   -- | Edge index-  m Int+  ST s Int addEdgeST MfGraph {..} from to cap = do   let !_ = ACIA.checkCustom "AtCoder.MaxFlow.addEdgeST" "`from` vertex" from "the number of vertices" nG   let !_ = ACIA.checkCustom "AtCoder.MaxFlow.addEdgeST" "`to` vertex" to "the number of vertices" nG@@ -327,9 +328,9 @@  {-# INLINEABLE flowST #-} flowST ::-  (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) =>+  (HasCallStack, Num cap, Ord cap, VU.Unbox cap) =>   -- | Graph-  MfGraph (PrimState m) cap ->+  MfGraph s cap ->   -- | Source @s@   Int ->   -- | Sink @t@@@ -337,7 +338,7 @@   -- | Flow limit   cap ->   -- | Max flow-  m cap+  ST s cap flowST MfGraph {..} s t flowLimit = stToPrim $ do   let !_ = ACIA.checkCustom "AtCoder.MaxFlow.flowST" "`source` vertex" s "the number of vertices" nG   let !_ = ACIA.checkCustom "AtCoder.MaxFlow.flowST" "`sink` vertex" t "the number of vertices" nG@@ -418,14 +419,14 @@  {-# INLINEABLE minCutST #-} minCutST ::-  (PrimMonad m, Num cap, Ord cap, VU.Unbox cap) =>+  (Num cap, Ord cap, VU.Unbox cap) =>   -- | Graph-  MfGraph (PrimState m) cap ->+  MfGraph s cap ->   -- | Source @s@   Int ->   -- | Minimum cut-  m (VU.Vector Bit)-minCutST MfGraph {..} s = stToPrim $ do+  ST s (VU.Vector Bit)+minCutST MfGraph {..} s = do   visited <- VUM.replicate nG $ Bit False   que <- ACIQ.new nG -- we could use a growable queue here   ACIQ.pushBack que s@@ -446,13 +447,13 @@  {-# INLINEABLE getEdgeST #-} getEdgeST ::-  (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) =>+  (HasCallStack, Num cap, Ord cap, VU.Unbox cap) =>   -- | Graph-  MfGraph (PrimState m) cap ->+  MfGraph s cap ->   -- | Vertex   Int ->   -- | Tuple of @(from, to, cap, flow)@-  m (Int, Int, cap, cap)+  ST s (Int, Int, cap, cap) getEdgeST MfGraph {..} i = stToPrim $ do   m <- ACIGV.length posG   let !_ = ACIA.checkEdge "AtCoder.MaxFlow.getEdge" i m@@ -463,27 +464,27 @@  {-# INLINEABLE edgesST #-} edgesST ::-  (PrimMonad m, Num cap, Ord cap, VU.Unbox cap) =>+  (Num cap, Ord cap, VU.Unbox cap) =>   -- | Graph-  MfGraph (PrimState m) cap ->+  MfGraph s cap ->   -- | Vector of @(from, to, cap, flow)@-  m (VU.Vector (Int, Int, cap, cap))+  ST s (VU.Vector (Int, Int, cap, cap)) edgesST g@MfGraph {posG} = do   len <- ACIGV.length posG-  VU.generateM len (getEdge g)+  EVP.generateM len (getEdge g)  {-# INLINEABLE changeEdgeST #-} changeEdgeST ::-  (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) =>+  (HasCallStack, Num cap, Ord cap, VU.Unbox cap) =>   -- | Graph-  MfGraph (PrimState m) cap ->+  MfGraph s cap ->   -- | Edge index   Int ->   -- | New capacity   cap ->   -- | New flow   cap ->-  m ()+  ST s () changeEdgeST MfGraph {..} i newCap newFlow = stToPrim $ do   m <- ACIGV.length posG   let !_ = ACIA.checkEdge "AtCoder.MaxFlow.changeEdgeST" i m

@@ -35,6 +35,7 @@ import Tests.Extra.Tree qualified import Tests.Extra.Tree.Lct qualified import Tests.Extra.Vector qualified+import Tests.Extra.Vector.Prim qualified import Tests.Extra.WaveletMatrix qualified import Tests.Extra.WaveletMatrix.BitVector qualified import Tests.Extra.WaveletMatrix.Raw qualified@@ -97,6 +98,7 @@             testGroup "Tree" Tests.Extra.Tree.tests,             testGroup "Tree.Lct" Tests.Extra.Tree.Lct.tests,             testGroup "Vector" Tests.Extra.Vector.tests,+            testGroup "Vector.Prim" Tests.Extra.Vector.Prim.tests,             testGroup "WaveletMatrix" Tests.Extra.WaveletMatrix.tests,             testGroup "WaveletMatrix.BitVector" Tests.Extra.WaveletMatrix.BitVector.tests,             testGroup "WaveletMatrix.Raw" Tests.Extra.WaveletMatrix.Raw.tests,