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

[Luke Palmer]

On Mon, Jun 27, 2011 at 4:25 PM, Twan van Laarhoven <twanvl at gmail.com>wrote:

> 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':
>

This is beginning to be reminiscent of the recent paper by Max Bolingbroke,
"termination combinators forever" (great paper).

http://www.cl.cam.ac.uk/~mb566/papers/termination-combinators-hs11.pdf


> > 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<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
>
>
> ______________________________**_________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110627/2f42c47d/attachment.htm>