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

From HaskellWiki

(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 |
+ | 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 |
+ | 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)
```