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

From HaskellWiki

(Implemented Floyd's cycle-finding algorithm) |
(Add case for non-cyclic lists of odd length.) |
||

Line 4: | Line 4: | ||

findCycle xxs = fCycle xxs xxs |
findCycle xxs = fCycle xxs xxs |
||

where fCycle _ [] = (xxs,[]) -- not cyclic |
where fCycle _ [] = (xxs,[]) -- not cyclic |
||

+ | fCycle _ [_] = (xxs,[]) -- not cyclic |
||

fCycle (x:xs) (_:y:ys) |
fCycle (x:xs) (_:y:ys) |
||

| x == y = fStart xxs xs |
| x == y = fStart xxs xs |

## Revision as of 15:11, 16 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 _ [] = (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)
```