On Mon, Jun 27, 2011 at 4:25 PM, Twan van Laarhoven <span dir="ltr">&lt;<a href="mailto:twanvl@gmail.com">twanvl@gmail.com</a>&gt;</span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

<div class="im">On 2011-06-27 13:51, Steffen Schuldenzucker wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Could you specify what exactly the function is supposed to do? I am<br>
pretty sure that a function like<br>
<br>
seqPeriod :: (Eq a) =&gt; [a] -&gt; Maybe Integer -- Nothing iff non-periodic<br>
<br>
cannot be written.<br>
</blockquote>
<br></div>
What about sequences that can be specified in terms of &#39;iterate&#39;:<br></blockquote><div><br></div><div>This is beginning to be reminiscent of the recent paper by Max Bolingbroke, &quot;termination combinators forever&quot; (great paper).</div>

<div><br></div><div><a href="http://www.cl.cam.ac.uk/~mb566/papers/termination-combinators-hs11.pdf">http://www.cl.cam.ac.uk/~mb566/papers/termination-combinators-hs11.pdf</a></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">


<br>
&gt; import Control.Arrow (first)<br>
<br>
&gt; -- Return the non-repeating part of a sequence followed by the repeating part.<br>
&gt; --<br>
&gt; -- &gt; iterate f x0 == in  a ++ cycle b<br>
&gt; -- &gt;  where (a,b) = findCycle f x0<br>
&gt; --<br>
&gt; -- see <a href="http://en.wikipedia.org/wiki/Cycle_detection" target="_blank">http://en.wikipedia.org/wiki/<u></u>Cycle_detection</a><br>
&gt; findCycle :: Eq a =&gt; (a -&gt; a) -&gt; a -&gt; ([a],[a])<br>
&gt; findCycle f x0 = go1 (f x0) (f (f x0))<br>
&gt;       where<br>
&gt;         go1 x y | x == y    = go2 x0 x<br>
&gt;                 | otherwise = go1 (f x) (f (f y))<br>
&gt;         go2 x y | x == y    = ([], x : go3 x (f x))<br>
&gt;                 | otherwise = first (x:) (go2 (f x) (f y))<br>
&gt;         go3 x y | x == y    = []<br>
&gt;                 | otherwise = y : go3 x (f y)<br>
&gt;<br>
&gt; -- diverges if not periodic<br>
&gt; seqPeriod :: Eq a =&gt; (a -&gt; a) -&gt; a -&gt; Integer<br>
&gt; seqPeriod f x0 = length . snd $ findCycle f x0<br><font color="#888888">
<br>
<br>
Twan</font><div><div></div><div class="h5"><br>
<br>
______________________________<u></u>_________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/<u></u>mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br>