Floyd's cycle-finding algorithm
Revision as of 15:24, 16 October 2011 by Csoroz (Simplify pattern-matching equations.)
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
This function is essentially the inverse of
cycle. I.e. if
ys don't have a common suffix and both are finite, we have that
findCycle (xs ++ cycle ys) == (xs,ys)