Generate infinite list from function results

Question

I have a function that takes an integer and returns a list of integers.

How do I efficiently map this function to an initial integer, then for each item of the resulting list that has not be previously mapped, apply the same function and essentially generate an infinite list.

E.g.

f :: Int -> [Int]
f 0 = [1,2]++(f 1)++(f 2)

Additionally, I need to be able to index the resulting list up to 10E10. How would this be optimised? memoization?

Answer 1

You want a breadth-first search. The basic idiom goes like this:

bfs :: (a -> [a]) -> [a] -> [a]
bfs f xs = xs ++ bfs f (concatMap f xs)

Notice how we keep the current "state" in the argument xs, output it and then recursively call with a new state which is f applied to each element of the input state.

If you want to filter out elements you haven't seen before, you need to also pass along some extra state keeping track of which elements you've seen, e.g. a Data.Set, and adjust the algorithm accordingly. I'll leave that bit to you because I'm an irritating pedagogue.