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

[Twan van Laarhoven]

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