# Floyd's cycle-finding algorithm

### From HaskellWiki

This is a Haskell impelementation of Floyd's cycle-finding algorithm for finding cycles in lists.

findCycle :: Eq a => [a] -> ([a],[a]) findCycle xxs = fCycle xxs xxs where fCycle (x:xs) (_:y:ys) | x == y = fStart xxs xs | otherwise = fCycle xs ys fCycle _ _ = (xxs,[]) -- not cyclic fStart (x:xs) (y:ys) | x == y = ([], x:fLength x xs) | otherwise = let (as,bs) = fStart xs ys in (x:as,bs) fLength x (y:ys) | x == y = [] | otherwise = y:fLength x ys

cycle

xs

ys

findCycle (xs ++ cycle ys) == (xs,ys)