Floyd's cycle-finding algorithm
Revision as of 21:07, 21 October 2007 by Twanvl (Implemented Floyd's cycle-finding algorithm)
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 (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)