list - Haskell，定义一个无限列表，动态添加数据并同时排序。如何？

Question

我必须定义一个列表，其中:

1是成员(member)

如果 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 -ing 树只是 listify -ing 两个分支，合并它们并将根放在开始处，即在上面的树中

1:merge (listify A) (listify B)

由于这是作业我就不多说了，但是树的任何一个分支都是完全由根节点决定的，所以 listify的类型签名可以 Integer -> [Integer] .一旦你有了 listify ，然后 theList = listify 1 .