Floyd's cycle-finding algorithm
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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 xs and ys don't have a common suffix and both are finite, we have that
findCycle (xs ++ cycle ys) == (xs,ys)