Can iterate be written with a fold?

Foreword

I was experimenting with the idea of repeatedly applying a function f to a given argument z, over and over, thus getting an infinite list.

Basically I want the list [z, f z, f (f z), f (f (f z)), ...], which I could feed to take n, takeWhile whatever, or something else.

Initially I thought that since the list I'm gonna deal with is infinite (I was thinking of repeat f), I should use foldr, but in reality that's not possible, because when foldring an infinite list the accumulator is usually set to undefined because unused, so in something like foldr (\f (x:xs) -> f x:x:xs) undefined (repeat f) I wouldn't have where to put z.

The question

So I started writing this question, and, thanks to the automatic suggestions that pop up, I discovered that iterate exists already, and its implementation is,

{-# NOINLINE [1] iterate #-}
iterate :: (a -> a) -> a -> [a]
iterate f x =  x : iterate f (f x)

so my question changed: is it possible to write iterate as a fold? If so, how? If not, why?

No, or at least not in any idiomatic way. But that's because foldr is the wrong tool for the job. foldr is a fold, or catamorphism. That's a fancy mathematical way of saying it takes aggregate data (in this case, a list) and produces a single result (a scalar, such as a number). This is why operations like sum are straightforward to write in terms of foldr, because sum fundamentally takes aggregate data and produces a singular result.

What you want is an anamorphism, or a way to take a single point of data (z in your example) and produce aggregate data from that. In Haskell, this is appropriately named unfoldr.

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 

unfoldr starts with ab initial value b and calls the function it's given. Each time it calls the function, if it produces a Just (a, b'), then we use a as the first element of the list and continue with b' as the state value. If the function returns Nothing, then we stop iterating.

In your case, you want to produce an infinite list, so we'll always return a Just value. You can write iterate in terms of unfoldr as follows.

import Data.List(unfoldr)

iterate' :: (a -> a) -> a -> [a]
iterate' f = unfoldr (\z -> Just (z, f z))