[Haskell-cafe] Period of a sequence

[Steffen Schuldenzucker]

On 06/26/2011 04:16 PM, michael rice wrote:
> MathWorks has the function seqperiod(x) to return the period of sequence
> x. Is there an equivalent function in Haskell?

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. If "sequences" are represented by the terms that 
define them (or this information is at least accessible), chances might 
be better, but I would still be interested how such a function works. 
The problem seems undecidable to me in general.

On finite lists (which may be produced from infinite ones via 'take'), a 
naive implementation could be this:

 >
 > import Data.List (inits, cycle, isPrefixOf)
 > import Debug.Trace
 >
 > -- Given a finite list, calculate its period.
 > -- The first parameter controls what is accepted as a generator. See 
below.
 > -- Set it to False when looking at chunks from an infinite sequence.
 > listPeriod :: (Eq a) => Bool -> [a] -> Int
 > listPeriod precisely xs = case filter (generates precisely xs) (inits 
xs) of
 >     -- as (last $ init xs) == xs, this will always suffice.
 >     (g:_) -> length g  -- length of the *shortest* generator
 >
 > -- @generates prec xs g@ iff @g@ generates @xs@ by repitition. If 
@prec@, the
 > -- lengths have to match, too. Consider
 > --
 > -- >>> generates True [1,2,3,1,2,1,2] [1,2,3,1,2]
 > -- False
 > --
 > -- >>> generates False [1,2,3,1,2,1,2] [1,2,3,1,2]
 > -- True
 > generates :: (Eq a) => Bool -> [a] -> [a] -> Bool
 > generates precisely xs g = if null g
 >     then null xs
 >     else (not precisely || length xs `mod` length g == 0)
 >       && xs `isPrefixOf` cycle g
 >

-- Steffen