In the same scenario as my previous question, I was trying to implement the cycle function only¹ using a fold, when I came up with the following wrong function, which tries to concatenate the accumulator with itself, building the infinite list exponentially (yes, I know this would mean that it generates 2048 copies if one wants to take 1025 of them)
myCycle :: [a] -> [a]
myCycle s = foldr (\_ a -> a ++ a) s [1..]
However, using it throws *** Exception: heap overflow.
This version, instead, works like a charm
myCycle :: [a] -> [a]
myCycle s = foldr (\_ a -> s ++ a) s [1..]
My question is, why does the former version overflow, as compared to the latter? I feel the reason is dumber than me...
[1] I mean, implementing cycle as a fold, having only the step function and the seed as degrees of freedom.
foldr c n takes a list and replaces every (:) with c and the final [] with n. But [1..] has no final [], so foldr (\_ a -> a ++ a) s has no place to put the s. Therefore no information ever "flows" from s to the result of myCycle s, which means it has no choice but to be bottom (or rather: it has too much choice—it's underspecified—so it gives up and falls back to bottom). The second version actually does use s, because it appears in the folding function, which is used when foldr acts on an infinite list.
In fact, we have the identity
foldr (\_ -> f) x xs = fix f = let x = f x in x
when xs is infinite. That is, the second argument of foldr is completely ignored when the list is infinite. Further, if that folding function doesn't actually look at the elements of the list, then all that's really happening is you're infinitely nesting f within itself: fix f = f (f (f (f ...))). fix is fundamental in the sense that every kind of recursion can be written in terms of it (certain more exotic kinds of recursion require adding some language extensions, but the definition fix f = let x = f x in x itself doesn't change). This makes writing any recursive function in terms of foldr and an infinite list trivial.
Here's my take on an exponential cycle. It produces 1 copy of the input, concatenated onto 2 copies, concatenated onto 4, etc.
myCycle xs = xs ++ myCycle (xs ++ xs)
You translate an explicitly recursive definition to fix by abstracting the recursive call as a parameter and passing that to fix:
myCycle = fix \rec xs -> xs ++ rec (xs ++ xs)
And then you use the foldr identity and introduce a bogus [] case
myCycle = foldr (\_ rec xs -> xs ++ rec (xs ++ xs)) (error "impossible") [1..]