如何在Haskell中创建无限重复列表？

Question

我是一名C#程序员，尝试通过Erik Meijer在Channel 9网站上的网络视频教程来自学Haskell。我遇到了一个有趣的难题，涉及使用zip和mod跳过列表中的每个'n'元素。

every :: Int -> [a] -> [a]
every _ [] = []
every n xs = [x | (x,i) <- zip xs [1..], i `mod` n == 0]

我一直在思考，如果我们能避免使用模（mod）运算符，在处理非常大的列表或流时就会更加高效。

我考虑过惰性地创建一个重复的整数列表，这样我们就可以简单地将 i 的值与 n 进行比较。

repeatInts :: Int -> [Int]

假设调用repeatInts 3会无限返回[1,2,3,1,2,3,1,2,3,1,2,3,..]。

鉴于此，我们可以重新定义every如下：

every :: Int -> [a] -> [a]
every _ [] = []
every n xs = [x | (x,i) <- zip xs (repeatInts n), i == n]

所以我的问题是：你会如何实现repeatInts函数？

- Damian Powell

---

参见：https://dev59.com/YXI-5IYBdhLWcg3wEEHu - Charles Stewart

Answer 1

使用 cycle 函数：

cycle :: [a] -> [a]  

cycle ties a finite list into a circular one, or equivalently, the infinite repetition of the original list. It is the identity on infinite lists.

您可以使用 cycle 定义 repeatInts ：

*Main> let repeatInts n = cycle [1..n]
*Main> :t repeatInts
repeatInts :: (Num t, Enum t) => t -> [t]
*Main> take 10 $ repeatInts 3
[1,2,3,1,2,3,1,2,3,1]

---

对于好奇的读者，GHC使用以下方式实现cycle:

cycle [] = errorEmptyList "cycle"
cycle xs = xs' where xs' = xs ++ xs'

在纯函数的术语中，这种奇特的技巧被称为“tying the knot”，它创建的是循环数据结构而不是无限的数据结构。

有关详细信息，请参见：

• Haskell wiki上的“Tying the Knot”
• GHC评论中的“Tying the Knot”
• Stack Overflow上的“tying the knot”的解释
• Stack Overflow标签[tying-the-knot]

- Greg Bacon

---

谢谢，gbacon。我就知道答案会很简单！现在我可以深入了解“cycle”的工作原理了。 - Damian Powell

有些奇怪的是，即使循环列表不是标准的 Haskell '98，但 cycle 却是标准的。请查看上面的源代码关于它所说的内容 - 你可能会或可能不会得到循环列表... - Charles Stewart

有趣的是，这个问答本身就是XY问题的一个实例。;) 在列表中跳过每个第n个元素不应该涉及任何mod，也不应该无限计数。正确的解决方案似乎是使用zip和(cycle $ (0 <$ [2..n]) ++ [1])，或者通过iterate和splitAt。 :) - Will Ness

Answer 2

晚了点回答，但也可以这样写：

repeatInts :: Int -> [Int]
repeatInts 0 = []
repeatInts a = [1..a] ++ repeatInts a

- Sam R.