Haskell, определите бесконечный список, добавляйте данные на лету и сортируйте одновременно.Как?

Question

Я должен определить список, в котором:

• 1 является членом
• если n является членом, то 2n + 1 и 3n + 1

Так что список бесконечен и должен быть отсортирован. При загрузке в GHCi команда:

"take 10 theList"

даст:

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

Ниже приведены мои коды:

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

Кажется, он работает, за исключением того, что он не отсортирован, выдает та же команда, что и выше:

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

У кого-нибудь есть идея с этим разобраться? Спасибо

Answer 1

Проблема может быть в виде бесконечного двоичного дерева (A и B - метки для ветвей):

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

Думая об этом таким образом, мы видим, что мы хотим написать функцию ("listify"), которая преобразует "дерево" в отсортированный список. Вот где Haskell действительно хорош: если у нас есть функция (merge), которая берет два (бесконечных) отсортированных списка и объединяет их в один отсортированный список (вы должны написать эту функцию), тогда listify - дерево просто listify - связывая две ветви, объединяя их и помещая корень в начало, то есть в дерево выше

1:merge (listify A) (listify B)

Поскольку это домашнее задание, я не буду говорить намного больше, но любая ветвь дерева полностью определяется корневым узлом, поэтому сигнатура типа listify может быть Integer -> [Integer]. И если у вас есть listify, тогда theList = listify 1.

Answer 2

Еще один способ увидеть это - отфильтрованный список целых чисел.Число n является частью последовательности, если n = 1 (mod 2) и (n-1) / 2 является частью последовательности, или если n = 1 (mod 3) и (n-1) / 3 являетсячасть последовательности.