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

1:merge (listify A) (listify B)

由于这是作业,我不会多说,但树的任何分支完全由根节点决定,因此类型签名listify可以是Integer -> [Integer].一旦你有了listify,那么theList = listify 1.