data-findcycle 0.1.1.0 → 0.1.2.0

raw patch · 5 files changed

+89/−68 lines, 5 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• CHANGELOG.md +9/−0
• bench/Main.hs +3/−3
• data-findcycle.cabal +1/−1
• src/Data/FindCycle.hs +73/−61
• test/Main.hs +3/−3

@@ -1,5 +1,14 @@ # Revision history for data-findcycle +## 0.1.2.0 -- 2025-05-31++* Correct unfortunate misspelling of "Nivasch" as "Nivash".+  New correctly named `nivasch*` functions were added. The old `nivash*` functions+  are deprecated and will be removed in 0.2.+* Fix documentation rendering issue caused by the introduction of LANGUAGE CPP+  by removing CPP. Turns out it wasn't really necessary to start with.+* Minor refactoring to improve test coverage.+ ## 0.1.1.0 -- 2025-04-24  * Add `nivashPart` and `nivashPartWithinBounds` as variants of `nivash` using

@@ -88,9 +88,9 @@ algs =     [ ("brent", brent)     , ("floyd", floyd)-    , ("nivash", nivash)-    , ("nivashPart", nivashPart (fromIntegral :: Int -> Word8))-    , ("nivashPartWithinBounds", nivashPartWithinBounds (0, 0xff) (.&. 0xff))+    , ("nivasch", nivasch)+    , ("nivaschPart", nivaschPart (fromIntegral :: Int -> Word8))+    , ("nivaschPartWithinBounds", nivaschPartWithinBounds (0, 0xff) (.&. 0xff))     , ("naiveHashable", naiveHashable)     , ("naiveOrd", naiveOrd)     ]

@@ -1,6 +1,6 @@ cabal-version:      1.18 name:               data-findcycle-version:            0.1.1.0+version:            0.1.2.0 synopsis:           Find cycles in periodic functions (and lists) description:   Any function @f :: a -> a@ where the type @a@ has finitely many values

@@ -1,12 +1,9 @@-{-# LANGUAGE CPP #-}-{-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE LambdaCase #-} {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE RecordWildCards #-} {-# LANGUAGE ScopedTypeVariables #-}-{-# LANGUAGE TypeFamilies #-}  {- |   Module: Data.FindCycle@@ -31,9 +28,9 @@        > fastCyclicFunc (10^100)         The length of the non-repeating prefix and the length of the cycle, as-       determined using the 'nivash' algorithm:+       determined using the 'nivasch' algorithm: -       > let (mu, lambda) = findCycle nivash someCyclicFunc startingValue+       > let (mu, lambda) = findCycle nivasch someCyclicFunc startingValue         The same two lengths, plus two lists containing the values of the prefix and        cyclic parts of the sequence using the 'naiveOrd' algorithm:@@ -70,7 +67,7 @@        All algorithms always provide a minimal \(\lambda\) as opposed to a        multiple of the true cycle length. -       In practice, you'll usually want to use 'nivash', 'brent', or one of the+       In practice, you'll usually want to use 'nivasch', 'brent', or one of the        naive variants. If performance matters and you're not sure what to choose,        compare the alternatives by benchmarking for your usecase.     -}@@ -114,9 +111,9 @@     floyd,      -- ** Memory/Time Compromise-    nivash,-    nivashPart,-    nivashPartWithinBounds,+    nivasch,+    nivaschPart,+    nivaschPartWithinBounds,      -- * Running algorithms     findCycle,@@ -127,6 +124,17 @@      -- * Utilities     minimalMu,++    -- * Deprecated++    {- |+       'nivasch' was originally misspelled as 'nivash' in various places, which is+       unfortunate. These old functions are deprecated and will be removed in the+       next major release.+    -}+    nivash,+    nivashPart,+    nivashPartWithinBounds, ) where  import Control.Applicative ((<*>), (<|>))@@ -141,10 +149,6 @@ import Data.Traversable (traverse) import Prelude hiding (traverse, (<$), (<$>), (<*>)) -#if __GLASGOW_HASKELL__ >= 800-import Data.Kind (Type)-#endif- data Input s a = Input     { inpUncons :: s -> Maybe (a, s)     , inpAdvance :: Int -> s -> s@@ -273,7 +277,7 @@   >>> -- cycle μ=1, λ=83333 when starting from 23   >>> let f :: Integer -> Integer; f x = x^(42 :: Int) `mod` 1000003   >>>-  >>> g = cycleExp nivash f 23+  >>> g = cycleExp nivasch f 23   >>> g 0 -- after 0 iterations   23   >>> -- after a googol iterations, but finishes in less than the current@@ -341,59 +345,46 @@ brent :: (Eq a) => CycleFinder a brent = CycleFinder brent' -#if __GLASGOW_HASKELL__ < 800-#define Type *-#endif--class NivashSt st m where-    type State st m a :: Type-    newSt :: st a -> m (State st m a)-    checkSt :: (Ord a) => st a -> a -> Int -> State st m a -> m (Either Int (State st m a))--#undef Type+class NivaschSt st m where+    checkSt :: (Ord a) => a -> Int -> st a -> m (Either Int (st a)) -data NivashStack a = NivashStack+data NivaschStack a = NivaschStack [(a, Int)] -instance (Monad m) => NivashSt NivashStack m where-    type State NivashStack m a = [(a, Int)]-    newSt _ = return []+instance (Monad m) => NivaschSt NivaschStack m where     {-# INLINE checkSt #-}-    checkSt _ x i xs+    checkSt x i (NivaschStack xs)         | (sx, si) : _ <- xs', sx == x = return (Left si)-        | otherwise = return . Right $ (x, i) : xs'+        | otherwise = return . Right . NivaschStack $ (x, i) : xs'       where         xs' = dropWhile ((> x) . fst) xs -data NivashMultiStack st k a = NivashMultiStack-    { partBounds :: (k, k)-    , partF :: a -> k-    , partDelegate :: st a+data NivaschMultiStack s k a = NivaschMultiStack+    { partF :: a -> k+    , partStacks :: A.STArray s k (NivaschStack a)     } -instance (A.Ix k, NivashSt st (ST s)) => NivashSt (NivashMultiStack st k) (ST s) where-    type State (NivashMultiStack st k) (ST s) a = A.STArray s k (State st (ST s) a)-    newSt NivashMultiStack{..} = newSt partDelegate >>= A.newArray partBounds+instance (A.Ix k) => NivaschSt (NivaschMultiStack s k) (ST s) where     {-# INLINE checkSt #-}-    checkSt NivashMultiStack{..} x i stacks =-        A.readArray stacks k-            >>= checkSt partDelegate x i-            >>= traverse ((stacks <$) . A.writeArray stacks k)+    checkSt x i ms@NivaschMultiStack{..} =+        A.readArray partStacks k+            >>= checkSt x i+            >>= traverse ((ms <$) . A.writeArray partStacks k)       where         k = partF x -{-# INLINE nivash' #-}-nivash' :: (Ord a, NivashSt st m, Monad m) => st a -> Input s a -> s -> m (Int, Int)-nivash' stack Input{..} = (newSt stack >>=) . flip (go 0)+{-# INLINE nivasch' #-}+nivasch' :: (Ord a, NivaschSt st m, Monad m) => st a -> Input s a -> s -> m (Int, Int)+nivasch' stack Input{..} = go 0 stack   where     go i st = maybe (return (i, 0)) (uncurry go') . inpUncons       where         go' x s =-            checkSt stack x i st >>= \case+            checkSt x i st >>= \case                 Left si -> return (si, i - si)                 Right st' -> go (i + 1) st' s  {- |-  Nivash's cycle finding algorithm.+  Nivasch's cycle finding algorithm.    Never computes an element at a given position in the sequence more than once. @@ -406,15 +397,15 @@    * [G. Nivasch, "Cycle detection using a stack", Information Processing Letters 90/3, pp. 135-140, 2004.](https://drive.google.com/file/d/16H_lrjeaBJqWvcn07C_w-6VNHldJ-ZZl/view) -}-nivash :: (Ord a) => CycleFinder a-nivash = CycleFinder $ (runIdentity .) . nivash' NivashStack+nivasch :: (Ord a) => CycleFinder a+nivasch = CycleFinder $ (runIdentity .) . nivasch' (NivaschStack [])  {- $   >>> :seti -XDataKinds -XTypeApplications -XFlexibleContexts -}  {- |-  Like 'nivash', but uses multiple independent stacks as determined by a partitioning+  Like 'nivasch', but uses multiple independent stacks as determined by a partitioning   function.    This trades off some additional memory usage for the ability to detect cycles earlier@@ -422,29 +413,29 @@    Using \(k\) stacks, the cycle will be identified after, on average, a fraction of   \(\dfrac{1}{k+1}\) of the cycle length. E.g 50% above the absolute minimum achievable-  for \(k=1\) ('nivash' without partitioning), or 1% above that minimum for \(k=99\).+  for \(k=1\) ('nivasch' without partitioning), or 1% above that minimum for \(k=99\).    The entire range of @k@ will be used for partitioning, with each value from 'minBound'   to 'maxBound' having its own partition. Use a type appropriate for the number of-  partitions you'd like to use. Use 'nivashPartWithinBounds' if you'd like to explicitly+  partitions you'd like to use. Use 'nivaschPartWithinBounds' if you'd like to explicitly   use a continuous subrange of @k@ instead.    >>> import Data.Word (Word8)-  >>> let alg256 = nivashPart (fromIntegral :: Integer -> Word8)+  >>> let alg256 = nivaschPart (fromIntegral :: Integer -> Word8)    >>> import Data.Finite (modulo) -- >= 0.2 for the Ix instance-  >>> let alg100 = nivashPart (modulo @100)+  >>> let alg100 = nivaschPart (modulo @100) -}-nivashPart :: (A.Ix k, Bounded k, Ord a) => (a -> k) -> CycleFinder a-nivashPart = nivashPartWithinBounds (minBound, maxBound)+nivaschPart :: (A.Ix k, Bounded k, Ord a) => (a -> k) -> CycleFinder a+nivaschPart = nivaschPartWithinBounds (minBound, maxBound)  {- |-  Like 'nivashPart', but allows for a specific continuous subrange of @k@ to be used for+  Like 'nivaschPart', but allows for a specific continuous subrange of @k@ to be used for   partitioning rather than creating a partition for each possible value of @k@. -  >>> let alg100 = nivashPartWithinBounds (0, 99) (`mod` 100)+  >>> let alg100 = nivaschPartWithinBounds (0, 99) (`mod` 100) -}-nivashPartWithinBounds ::+nivaschPartWithinBounds ::     forall k a.     (A.Ix k, Ord a) =>     {- |@@ -458,8 +449,10 @@     -}     (a -> k) ->     CycleFinder a-nivashPartWithinBounds bounds f = CycleFinder $ \inp s ->-    runST $ nivash' (NivashMultiStack bounds f NivashStack) inp s+nivaschPartWithinBounds bounds f = CycleFinder $ \inp s ->+    runST $ do+        arr <- A.newArray bounds (NivaschStack []) :: ST s (A.STArray s k (NivaschStack a))+        nivasch' (NivaschMultiStack f arr) inp s  -- TODO: Gosper? maybe not really that useful in practice. -- TODO: Sedgewick, Szymanski, Yao@@ -506,7 +499,6 @@ minimalMu :: forall a. (Eq a) => CycleFinder a -> CycleFinder a minimalMu alg = CycleFinder go   where-    go :: forall s. Input s a -> s -> (Int, Int)     go inp@Input{..} s = maybeFindMu (runCycleFinder alg inp s)       where         maybeFindMu r@(_, lambda)@@ -518,3 +510,23 @@             go' (t, ts') (m, ms')                 | t == m = mu                 | otherwise = findMu (mu + 1) ts' ms'++{-# DEPRECATED+    nivash+    , nivashPart+    , nivashPartWithinBounds+    "Use nivasch* functions instead"+    #-}++-- | Alias for 'nivasch'.+nivash :: (Ord a) => CycleFinder a+nivash = nivasch++-- | Alias for 'nivaschPart'.+nivashPart :: (A.Ix k, Bounded k, Ord a) => (a -> k) -> CycleFinder a+nivashPart = nivaschPart++-- | Alias for 'nivaschPartWithinBounds'.+nivashPartWithinBounds ::+    forall k a. (A.Ix k, Ord a) => (k, k) -> (a -> k) -> CycleFinder a+nivashPartWithinBounds = nivaschPartWithinBounds

@@ -62,9 +62,9 @@ partialAlgs :: AlgClass (Labeled (CycleFinder Integer)) partialAlgs =     AlgClass-        (Labeled "nivash" nivash)-        [ Labeled "nivashPart" (nivashPart (fromIntegral :: Integer -> Word8))-        , Labeled "nivashPartWithinBounds" (nivashPartWithinBounds (0, 99) (`mod` 100))+        (Labeled "nivasch" nivasch)+        [ Labeled "nivaschPart" (nivaschPart (fromIntegral :: Integer -> Word8))+        , Labeled "nivaschPartWithinBounds" (nivaschPartWithinBounds (0, 99) (`mod` 100))         , Labeled "brent" brent         , Labeled "floyd" floyd         ]