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