On Mon, Jun 27, 2011 at 4:25 PM, Twan van Laarhoven <twa...@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@haskell.org > http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe> >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe