# [Haskell-cafe] Fwd: Re: Period of a sequence

Twan van Laarhoven twanvl at gmail.com
Tue Jun 28 00:25:33 CEST 2011

```On 2011-06-27 13:51, Steffen Schuldenzucker wrote:
> Could you specify what exactly the function is supposed to do? I am
> pretty sure that a function like
>
> seqPeriod :: (Eq a) => [a] -> Maybe Integer -- Nothing iff non-periodic
>
> cannot be written.

What about sequences that can be specified in terms of 'iterate':

> import Control.Arrow (first)

> -- Return the non-repeating part of a sequence followed by the repeating part.
> --
> -- > iterate f x0 == in  a ++ cycle b
> -- >  where (a,b) = findCycle f x0
> --
> -- see http://en.wikipedia.org/wiki/Cycle_detection
> findCycle :: Eq a => (a -> a) -> a -> ([a],[a])
> findCycle f x0 = go1 (f x0) (f (f x0))
>       where
>         go1 x y | x == y    = go2 x0 x
>                 | otherwise = go1 (f x) (f (f y))
>         go2 x y | x == y    = ([], x : go3 x (f x))
>                 | otherwise = first (x:) (go2 (f x) (f y))
>         go3 x y | x == y    = []
>                 | otherwise = y : go3 x (f y)
>
> -- diverges if not periodic
> seqPeriod :: Eq a => (a -> a) -> a -> Integer
> seqPeriod f x0 = length . snd \$ findCycle f x0

Twan

```