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

[Steffen Schuldenzucker]

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