«
»

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?

«
»

This entry was posted on Saturday, January 24th, 2009 at 10:31 AM and is filed under Haskell. You can follow any responses to this entry through the Atom feed. You can skip to the end and make a comment. Pinging is currently not allowed.

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

  1. Michael Day Says:
    January 24th, 2009 at 6:23 PM

    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:
    January 24th, 2009 at 6:34 PM

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

  3. Michael Day Says:
    January 25th, 2009 at 1:33 AM

    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:
    March 7th, 2015 at 5:01 PM

    @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/

Leave a Reply