This is not an issue, because lists are lazy. foldr does build lists ‘from the left’ (if by that you mean that the first subexpression to be reduced when the entire fold is reduced is the one involving the leftmost element), but that doesn’t mean that an infinite suffix has to be fully computed before it’s used.
You do want foldr for this, as well as recursion. The best way to think about foldr is as specifying a homogeneous replacement for the (:) and [] constructors in the list you provide to it. Can you think of a way to express what cycle does in terms of replacing every (:) in the provided list with something, and replacing the [] in the provided list with something else?