Haskell, define an infinite list, add data on the fly and sort at the same time. How?

Question

I have to define a list in which:

• 1 is a member
• if n is a member, so are 2n+1 and 3n+1

So the list is infinite and must be sorted. When loaded to GHCi, the command:

"take 10 theList"

will produce:

[1,3,4,7,9,10,13,15,19,21]

Below are my codes:

theList = ([1] ++ concat [[(x*2+1),(x*3+1)]|x<-theList])

It seems to work except for that it is not sorted, the same command as above produces:

[1,3,4,7,10,9,13,15,22,21]

Does anyone have any idea to sort that out? Thanks

Answer 1

The problem can be though of as a infinite binary tree (A and B are labels for the branches):

  1__ B
  |  4___
  |   \  13 ...
A 3_   \
  | \   9 ...
  7  10
  ...

Thinking about it this way, we can see that we want to write a function ("listify") that converts the "tree" into a sorted list. This is where Haskell is really nice: if we have a function (merge) that takes two (infinite) sorted lists and merges them into one sorted list (you should write this function), then listify-ing the tree is simply listify-ing the two branches, merging them and putting the root at the start, i.e. in the tree above

1:merge (listify A) (listify B)

Since this is homework I won't say much more, but any branch of the tree is entirely determined by the root node, so the type signature of listify can be Integer -> [Integer]. And once you have listify, then theList = listify 1.

Answer 2

Another way of seeing this is as a filtered list of integers. The number n is part of the sequence if n = 1 (mod 2) and (n-1)/2 is a part of the sequence, or if n = 1 (mod 3) and (n-1)/3 is a part of the sequence.