自生成列表,其中每个元素将一些元素附加到末尾

Question

我正在寻找一种方法来做这样的事情.假设我们从1开始.对于每个数字奇数,我们将它+5添加到列表的末尾.对于每个偶数,我们将它添加+3,将+7添加到列表的末尾.列表看起来像这样

[1,6,9,13,14,18,17,21,21,25,......]

我如何在Haskell中做这样的事情？

我知道你可以列出一个列表,其中每个元素都依赖于前面的元素,但是当多个元素依赖于同一元素时你是如何做到的,除非你开始,否则你不知道哪个元素取决于哪个元素从最开始？

Answer 1

以下解决方案使用自引用惰性列表,因此@GaneshSittampalam没有解决方案的线性时间问题:

xs = 1 : concatMap extras xs where
  extras x
    | odd x     = [x+5]
    | otherwise = [x+3,x+7]

Answer 2

如果一次只生成一个元素,它与你如何做它非常相似.在这种情况下,您将传递单个值以跟踪下一个元素的"种子".在这种情况下,您只需传递一个列表:

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]

一般的想法是,process包含我们知道的所有数字的参数应该在输出列表中,但是我们还没有添加"结果"数字.为了取得进展,我们检查其中的第一个,通过将其置于结果的头部来"输出"它,并计算随后的数字并将它们放入等待处理的列表中.通过将它们放在最后,我们确保一切都可以轮到我们.

请注意,使用naive list concatenation将它们放在最后意味着该算法在技术上会花费线性时间来通过列表生成下一个数字.这可以通过使用更有效的数据结构来处理,例如Data.Sequence.