Floyd's cycle-finding algorithm

From HaskellWiki
Revision as of 15:11, 16 October 2011 by Csoroz (talk | contribs) (Add case for non-cyclic lists of odd length.)

Jump to: navigation, search

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 xs and ys don't have a common suffix and both are finite, we have that

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