CODEWITHSUNDEEP
haskell
Luka Horvat
Luka Horvat

Reputation: 4402

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

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?

Upvotes: 7

Views: 225

Answers (3)

Ørjan Johansen
Ørjan Johansen

Reputation: 18189

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]

Upvotes: 13

Ganesh Sittampalam
Ganesh Sittampalam

Reputation: 29100

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.

Upvotes: 7

Jean-Bernard Pellerin
Jean-Bernard Pellerin

Reputation: 12670

My Haskell sucks so here's an outline with fake code.

You can do it with a filter.

Note that for any odd number: 2x+1
You'll add 2x+6 to your list

For ever even number: 2x
You'll add 2x+3 and 2x+7

so:

filter (f) naturalNumbers

where f(x) :  
  true if (x-7) % 2 == 0
  true if (x-6) % 2 == 0
  true if (x-3) % 2 == 0
  false otherwise

Upvotes: 0

Related Questions