Construction of infinite list in Haskell

Question

I have two things for the desired infinite list: its first element

x :: A

and function which generates the next element

f :: [A] -> A

What's the best (most idiomatic? fastest?) way to create infinite list? I mean

xs = x : f [x] : f [x, f [x]] : f [x, f [x], f [x, f [x]]] : ...

Answer 1

The function you want can be implemented as:

constructInf :: ([a] -> a) -> a -> [a]
constructInf f x = xs
  where xs = x:map f (tail $ inits xs)

The performance of consrtuctInf depends on the performance of it's argument function f. Assuming f takes O(N) time, then constructInf will take O(M*N) time, where M is the number of elements from the result of constructInf that you will inspect.