Difference between revisions of "Floyd's cycle-finding algorithm"
Jump to navigation
Jump to search
(Simplify pattern-matching equations.) |
(elements must be unique, e.g. findCycle $ cycle [0,1,0]) |
||
Line 15: | Line 15: | ||
</haskell> |
</haskell> |
||
− | This function is essentially the inverse of <hask>cycle</hask>. I.e. if <hask>xs</hask> and <hask>ys</hask> don't have a common suffix and both are finite, we have that |
+ | This function is essentially the inverse of <hask>cycle</hask>. I.e. if <hask>xs</hask> and <hask>ys</hask> don't have a common suffix, their elements are unique and both are finite, we have that |
<haskell> |
<haskell> |
||
findCycle (xs ++ cycle ys) == (xs,ys) |
findCycle (xs ++ cycle ys) == (xs,ys) |
Revision as of 16:38, 17 October 2011
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 xs
and ys
don't have a common suffix, their elements are unique and both are finite, we have that
findCycle (xs ++ cycle ys) == (xs,ys)