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