Skip to content

Instantly share code, notes, and snippets.

@rjkat
Created June 3, 2012 15:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rjkat/2863841 to your computer and use it in GitHub Desktop.
Save rjkat/2863841 to your computer and use it in GitHub Desktop.
Uses Brent's Algorithm to compute the cycle length and offset of a function
import Data.List
alphaWrap :: Char -> Char
alphaWrap c
| c == 'z' = 'a'
| 'a' <= c && c < 'z' = succ c
| otherwise = '?'
cycleLength :: Eq a => (a -> a) -> a -> Int
cycleLength f x = last $ 1 : unfoldr (cycleLength' f) (1, 1, x, f x)
cycleLength' f (power, l, tortoise, hare)
| tortoise == hare = Nothing
| power == l = Just (1, (power * 2, 1, hare, f hare))
| otherwise = Just (l + 1, (power, l + 1, tortoise, f hare))
cycleOffset :: Eq a => (a -> a) -> a -> Int
cycleOffset f x = length . takeWhile (uncurry (/=)) $ values
where values = iterate (pairMap f) (x, f' x)
f' = foldr (.) id (replicate n f)
n = cycleLength f x
pairMap f (a, b) = (f a, f b)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment