This post originated from an RSS feed registered with Java Buzz by Elliotte Rusty Harold. Original Post: Hypothesis: cycles cannot be implemented only with folds Feed Title: Mokka mit Schlag Feed URL: http://www.elharo.com/blog/feed/atom/? Feed Description: Ranting and Raving Latest Java Buzz Posts Latest Java Buzz Posts by Elliotte Rusty Harold Latest Posts From Mokka mit Schlag

The cycle function turns a list into an infinite list by repeating it. For instance, cycle [1,2,3] is [1,2,3,1,2,3,1,2,3...]. I could be wrong but I don’t think you can do this one purely with folds and here’s why:

1. The infinite list would have to be the accumulator.
2. A fold (foldr or foldl) operation steps over (processes) each element of the finite input list exactly once.
3. Each step can insert only a finite number of elements into the accumulator list.
4. Thus the final accumulated list must be finite.

Of course, Murphy’s Law guarantees that someone is now going to post a cycle implementation with pure folds in the comments. If there’s a mistake in this proof, it’s in step 3. But it really feels to me like a fold alone won’t do the trick. You have to use recursion of some sort here. Maybe a fold of folds? What if the step function is itself a fold?