Floyd's cycle-finding algorithm
Revision as of 15:11, 16 October 2011 by Csoroz (Add case for non-cyclic lists of odd length.)
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 _  = (xxs,) -- not cyclic fCycle _ [_] = (xxs,) -- not cyclic fCycle (x:xs) (_:y:ys) | x == y = fStart xxs xs | otherwise = fCycle xs ys 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)