# Cycle Detection

### The Algorithm

We can use Brent’s Algorithm to detect infinitely-repeating sequences in a list of values generated by some iterated function: that is, any list in which the next value in the sequence is generated from the previous value alone; if we find duplicate values in the list, we know we have a cycle.

The implementation below isn’t particularly elegant, and since I want to use it as a stand-alone tool I’m having it output strings:

```
module Main
where
cycling :: (Show a, Eq a) => Int -> [a] -> String
cycling k [] = "Empty list"
cycling k (a:as) = find 0 a 1 2 as
where find _ _ c _ [] = "reached end at " ++ show c ++": no cycles"
find i x c p (x':xs)
| c > k = "no cycles after " ++ show k
| x == x' = "cycle at "++ show c ++": "++(show$take (c-i) xs)
| c == p = find c x' (c+1) (p*2) xs
| otherwise = find i x (c+1) p xs
--- SOME RANDOM NUMBER GENERATORS TO TEST ---
-- bad generators?:
g1 = 0 : [ (g*7 + 1) `mod` 32 | g <- g1]
g2 = 17 : [ (g*22 + 221) `mod` 2^32 | g <- g2]
g3 = 3249 : [ (g*22695477 + 1) `mod` 300 | g <- g3]
g4 = 234587 : [ (g*22695476 + 1) `mod` 2^32 | g <- g4]
-- good generators:
g5 = 294587 : [ (g*22695477 + 1) `mod` 2^32 | g <- g5]
g6 = 0 : [ (g*22695477 + 1) `mod` 2^32 | g <- g6]
```

### Randomness is hard…

Linear Congruential Generator’s are
notoriously easy to screw up
with the wrong parameters. Let’s use our function to test just how
finicky this RNG algorithm can be. random stream `g4`

is almost identical to
`g5`

, a known-good generator. Let’s compare the two with a cut off limit of
999,999. First the good:

```
*Main> cycling 999999 g5
"no cycles after 999999"
```

Great, now let’s see how our typo-ed generator fares:

```
*Main> cycling 999999 g4
"cycle at 17: [180790021]"
```

… yikes.