Difference between revisions of "Floyd's cycle-finding algorithm"

From HaskellWiki
Jump to: navigation, search
(Add case for non-cyclic lists of odd length.)
m (Fix typo)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
This is a Haskell impelementation of [http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm Floyd's cycle-finding algorithm] for finding cycles in lists.
+
This is a Haskell implementation of [http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm Floyd's cycle-finding algorithm] for finding cycles in lists.
 
<haskell>
 
<haskell>
 
findCycle :: Eq a => [a] -> ([a],[a])
 
findCycle :: Eq a => [a] -> ([a],[a])
 
findCycle xxs = fCycle xxs xxs
 
findCycle xxs = fCycle xxs xxs
where fCycle _ [] = (xxs,[]) -- not cyclic
+
where fCycle (x:xs) (_:y:ys)
fCycle _ [_] = (xxs,[]) -- not cyclic
 
fCycle (x:xs) (_:y:ys)
 
 
| x == y = fStart xxs xs
 
| x == y = fStart xxs xs
 
| otherwise = fCycle xs ys
 
| otherwise = fCycle xs ys
  +
fCycle _ _ = (xxs,[]) -- not cyclic
 
fStart (x:xs) (y:ys)
 
fStart (x:xs) (y:ys)
 
| x == y = ([], x:fLength x xs)
 
| x == y = ([], x:fLength x xs)
Line 14: 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)

Latest revision as of 00:39, 5 February 2019

This is a Haskell implementation 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)