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.

Answer 2

You want iterate.

take 10 $ iterate (+1) 0

= [0,1,2,3,4,5,6,7,8,9]

If you need the whole list so far, and don't mind getting it reversed, you can do this:

mkl f x0 = x0 : unfoldr (\xs -> let x = f xs in Just (x, x:xs)) [x0]

If you need the whole list so far, and you want it in order, it will be really inefficient, but you can do this:

mkl' f x0 = x0 : unfoldr (\xs -> let x = f xs in Just (x, xs ++ [x])) [x0]

But I'm not sure why you need the whole list instead of just the last element.