Hi Thomas and Richard,
[...] Here's a piece of computer science that I would like some help with. I call it the Indirect Cycle Detection problem.
Given: Domains P and E, functions f : P -> Maybe P g : P -> E
Define to_list :: Maybe P -> [E] to_list Nothing = [] to_list (Just p) = g p : to_list (f p)
Given: That f is cyclic starting at p0.
Find: The shortest alpha, beta such that to_list p0 is alpha ++ cycle beta and do so *efficiently*.
Now, I can use tortoise-and-hare to find a cycle in f and then use brute force to find a shortest prefix and cycle of to_list ... The stuff I've checked so far about periods in strings has nothing to say about periods that begin _after_ a non-empty prefix.
As Thomas explained, that's sufficient. The tortoise-and-hare algorithm will identify a tail of the sequence that is known to be periodic, and then we can find the smallest period using an algorithm that operates on a finite string. Once the actual cycle length is known, identifying the prefix is easy.
Also, I can not see where this "non-empty prefix" notion comes from. Perhaps you have a different definition for cyclic?
See http://en.wikipedia.org/wiki/Cycle_detection .
In this case, ps has the form (prefix ++ (cycle p_period_n)) and to find this structure, you need to find the first element of ps that occurs twice. (Before, you knew this would be p0.) For that, you need a set implementation for elements of P that gives you efficient adding of one element and lookup. Since we know nothing about P's elements, we use the list itself and get a runtime of Theta((i+n)^2).
The tortoise-and-hare algorithm does this in O(i+n) time. I'm attaching some code. For simplicity, it works with functions @f :: a -> a@, @g :: a -> b@, which define the sequence @xs = map g (iterate f x)@. I'm using Brent's algorithm [1] for cycle detection, which finds the period and a periodic suffix of @iterate f x@, followed by Duval's algorithm [2] to identify the actual cycle length of @xs@. (The main advantage of Duval's algorithm over Knuth-Morris-Pratt is that less space is required. One disadvantage is that we need a total order on @b@.) The total running time is linear in the cycle length and initial prefix length of @iterate f x@, i.e. O(i+n). There are two entry points of interest in the code. - factor f g x Find prefix and repeated segment of @map g (iterate f x)@. - factor' f g x Find prefix and repeated segment of @to_list x@. The repeated segment will be empty if @to_list x@ is a finite list. Cheers, Bertram [1] http://en.wikipedia.org/wiki/Cycle_detection [2] http://stackoverflow.com/questions/3459509/minimal-cyclic-shift-algorithm-ex...