Self generating list where each element appends some elements to the end

Question

I'm looking for a way to do something like this. Say we start with 1. For every number odd number we add it +5 to the end of the list. For every even number we add it +3 and it +7 to the end of the list. The list would look like this

[1, 6, 9, 13, 14, 18, 17, 21, 21, 25,...]

How would I go about doing something like this in Haskell?

I'm aware that you can make a list where each element depends on the previous ones, but how do you do it when more than one element depends on the same one, and you don't know which group depends on which unless you start from the beginning?

Answer 1

The following solution uses a self-referencing lazy list, and so doesn't have the linear time problem of the solution by @GaneshSittampalam:

xs = 1 : concatMap extras xs where
  extras x
    | odd x     = [x+5]
    | otherwise = [x+3,x+7]

Answer 2

It's quite similar to how you would do it if only a single element was being generated at a time. In that case you would pass down a single value to keep track of the "seed" for the next elements. In this situation you can just pass down a list instead:

xs = process [1]

-- notice no [] case as we don't expect it to be needed
process (n:ns) = n:process (ns ++ extras)
  where
   extras
     | n `mod` 2 == 0 = [n+3, n+7]
     | otherwise = [n+5]

The general idea is that the argument to process contains all the numbers that we know should be in the output list, but for which we haven't yet added the "consequent" numbers. To make progress, we inspect the first of those, "output" it by putting it at the head of the result, and calculate the consequent numbers and put those into the list that's waiting to be processed. By putting them at the end we make sure that everything gets its turn, so to speak.

Note that putting them at the end using naive list concatenation means that this algorithm will technically take linear time in how far it's got through the list to produce the next number. This can be handled by using a more efficient data structure such as Data.Sequence.