# Hypothesis: cycles cannot be implemented only with folds

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?

### 4 Responses to “Hypothesis: cycles cannot be implemented only with folds”

1. Michael Day Says:

Here is a different way of looking at it: foldr can implement append, and cycle is simply appending itself to the end of the list. For example, consider `foldr (:) [4,5,6] xs`, this will append [4,5,6] to the end of xs. (Technically it creates a new list by replacing each cons with cons and the nil at the end with [4,5,6]). Since we can do append, all we need to do is append ourselves to the end of the list:

myCycle xs = foldr (:) (myCycle xs) xs

2. Elliotte Rusty Harold Says:

Yes, but that’s recursively calling the `myCycle` function. The infinity comes from the recursion, not `foldr`.

3. Michael Day Says:

Alright, how about this: you’ve assumed that the input list is finite. What if we pass in an infinite input list, and use that to repeatedly append the cycling list:

myCycle xs = foldr (step xs) [] [1..]
where step xs x acc = xs ++ acc

Is this cheating? We have to sneak infinity in there somehow :)

4. Erik Says:

@Michael thanks, this lead me to realize an important, initially seemingly unintuitive, property of foldr and foldl: http://lambda.jstolarek.com/2012/09/why-foldr-works-for-infinite-lists-and-foldl-doesnt/