在Haskell中扩展一个列表的列表

Question

有没有办法在Haskell中扩展列表？

我正在尝试编写一个生成[1,2,2,3,3,3,4,4,4,4.....]的函数，它基本上是1个1，2个2，3个3等。

我的尝试：

nnss :: [Integer]
nnss = [nPrint x x | x <- [1,2..]]

我的尝试存在问题，nPrint x x 返回一个整数列表，例如，nPrint 2 2会返回[2, 2]。有没有办法将列表从[1,2,3...]扩展到[1,2,2,3,3,3...]？

- rlhh

---

“nPrint”对于这个（打印是IO操作）来说是一个不好的名称，你应该使用的基本上只是“replicate”。 - leftaroundabout

Answer 1

我们要查找的函数签名是[[a]] -> [a]，如果我们检查 hoogle ，我们会发现concat就是我们要找的函数。

在这种情况下，列表推导式是不必要的，因为我们只需要迭代每个项，所以我们真正想要做的是一个map。由于结合map和concat是如此常见，我们可以直接编写：

concatMap (\x -> nPrint x x) [1..]

如果您对Haskell不熟悉，可以忽略这部分内容。由于列表单子是用concatMap定义的，所以我们也可以写成：

[1..] >>= \x -> nPrint x x

- Daniel Gratzer

---

如果我们真的想要进行 Haskell 代码的竞技，我们可以使用 [1..] >>= join replicate。这里使用了 Control.Monad 库中的 join 函数（在这个例子中是针对 (r -> r -> a) -> r -> a 类型的 ((->) r) 单子实例的）和之前提到的 replicate 函数。这样做可以让代码更短小精悍。 - Luis Casillas

Answer 2

您也可以不使用地图和列表连接来编写它（只需在常量时间内预先添加）：

nnss :: [Integer]
nnss = genRepeated 1 1

genRepeated :: Integer -> Integer -> [Integer]
genRepeated x 0 = genRepeated (x+1) (x+1)
genRepeated x y = x : genRepeated x (y-1)

Than

take 22 nnss == [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7]

---

另一个快速的可能性是：

其他快速的可能性是：

nnss :: [Integer]
nnss = flatten [take x $ repeat x | x <- [1..]]

flatten :: [[a]] -> [a]
flatten [] = []
flatten ([]:xs) = flatten xs
flatten ((x:xs):ys) = x : flatten (xs:ys)

- kyticka

---

当我对其进行性能分析时，这两个选项都比上述代码慢。 - daniel gratzer

@jozefg 噢，是渐进地还是常数倍的慢？你知道为什么吗？我并不是说它更快，只是更适合初学者，但我对造成差异的原因很感兴趣。 - kyticka

提醒一下，你自定义的函数 flatten 其实就是 concat：http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:concat - stusmith

Answer 3

只需添加concat：

nnss :: [Integer]
nnss = concat [nPrint x x | x <- [1,2..]]

- md2perpe