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

Steffen Schuldenzucker sschuldenzucker at uni-bonn.de
Mon Jun 27 13:51:33 CEST 2011

```Forwarding to -cafe

-------- Original Message --------
Subject: 	Re: [Haskell-cafe] Period of a sequence
Date: 	Mon, 27 Jun 2011 04:46:10 -0700 (PDT)
From: 	michael rice <nowgate at yahoo.com>
To: 	Steffen Schuldenzucker <sschuldenzucker at uni-bonn.de>

Hi Steffen,

Repeating decimals.

5/7 == 0.714285 714285 7142857 ... Period = 6

It does seem like a difficult problem.

This one is eventually repeating, with Period = 3

3227/555 = 5.8144 144 144…

Michael

--- On *Mon, 6/27/11, Steffen Schuldenzucker
/<sschuldenzucker at uni-bonn.de>/*wrote:

From: Steffen Schuldenzucker <sschuldenzucker at uni-bonn.de>
Subject: Re: [Haskell-cafe] Period of a sequence
To: "michael rice" <nowgate at yahoo.com>
Cc: haskell-cafe at haskell.org
Date: Monday, June 27, 2011, 4:32 AM

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

```

More information about the Haskell-Cafe mailing list