Haskell

Question

在Haskell中，可以像这样定义无限列表：

[1.. ]

如果找到许多描述如何实现无限列表的文章并且我理解了它是如何工作的。但是，我想不出有什么理由使用无限数据结构的概念。

谁能给我一个问题的例子，在 Haskell 中使用无限列表可以更容易地（或者也许只能）解决这个问题？

Answer 1

Haskell 中列表的基本优点是它们是一个 control 结构，看起来像 data 结构.您可以编写对流数据进行增量操作的代码，但它 看起来 就像对列表的简单操作。这与需要使用显式增量结构的其他语言形成对比，例如迭代器（Python 的 itertools）、协程（C# IEnumerable）或范围 (D)。

例如，sort 函数可以这样编写，即在开始生成结果之前对尽可能少的元素进行排序。虽然对 entire 列表进行排序需要 O(n log n) / 列表长度的线性时间，但 minimum xs = head (sort xs) 只需要 O(n) / linear 时间，因为 head 只会检查列表的第一个构造函数，如 x : _，并将 tail 保留为代表排序操作的剩余部分。

这意味着性能是组合：例如，如果您对数据流有很长的操作链，例如sum . map (* 2) . filter (< 5)，它看起来它会首先过滤所有元素，然后在它们上面映射一个函数，然后求和，在每一步产生一个完整的中间列表。但是发生的是每个元素一次只处理一个：给定 [1, 2, 6]，这基本上按如下方式进行，所有步骤都是递增的：

总计 = 0
1 < 5 为真
1 * 2 == 2
总计 = 0 + 2 = 2
2 < 5 为真
2 * 2 == 4
总计 = 2 + 4 = 6
6 < 5 为假
结果 = 6

这正是您用命令式语言（伪代码）编写快速循环的方式：

total = 0;
for x in xs {
  if (x < 5) {
    total = total + x * 2;
  }
}

这意味着性能是组合的：由于懒惰，这段代码在处理列表的过程中一直使用内存。 map 或 filter 内部没有什么特别之处可以实现这一点：它们可以完全独立。

再比如，标准库中的and计算列表的逻辑与，例如and [a, b, c] == a && b && c，它被简单地实现为折叠：and = foldr (&&) True。当它到达输入中的 False 元素时，它会停止求值，这仅仅是因为 && 在其正确的参数中是惰性的。懒惰给你作文！

有关所有这一切的优秀论文，请阅读 John Hughes 的著名 Why Functional Programming Matters，它超越了惰性函数式编程（在 Miranda 中，Haskell 的前身）的优点，远远优于我可以。

Answer 2

临时使用索引的无限列表来注释列表：

zip [0..] ['a','b','c','d'] = [(0,'a'), (1,'b'), (2,'c'), (3,'d')]

Memoizing 函数，同时保持纯度（在这种情况下，这种转换导致指数速度增加，因为 memo table 是递归使用的）：

fib = (memo !!)
    where
    memo = map fib' [0..]  -- cache of *all* fibonacci numbers (evaluated on demand) 
    fib' 0 = 0
    fib' 1 = 1
    fib' n = fib (n-1) + fib (n-2)

具有副作用的纯模拟程序（免费 monad）
```
data IO a = Return a
          | GetChar (Char -> IO a)
          | PutChar Char (IO a)
```
潜在的非终止程序用无限的IO结构表示；例如forever (putChar 'y') = PutChar 'y' (PutChar 'y' (PutChar 'y' ...))
尝试：如果您定义的类型大致如下所示：
```
data Trie a = Trie a (Trie a) (Trie a)
```
它可以表示由自然索引的 a 的无限集合。请注意，递归没有基本情况，因此每个 Trie 都是无限的。但是可以在 log(n) 时间内访问索引 n 处的元素。这意味着你可以这样做（使用 inttrie 库中的一些函数）：
```
findIndices :: [Integer] -> Trie [Integer]
findIndices = foldr (\(i,x) -> modify x (i:)) (pure []) . zip [0..]
```
这构建了一个高效的 "reverse lookup table"，给定列表中的任何值可以告诉您它出现在哪些索引处，并且它两者缓存结果并且在信息可用时立即流式传输信息：
```
-- N.B. findIndices [0, 0,1, 0,1,2, 0,1,2,3, 0,1,2,3,4...]
> table = findIndices (concat [ [0..n] | n <- [0..] ])
> table `apply` 0
[0,1,3,6,10,15,21,28,36,45,55,66,78,91,...
```
全部来自单线无限折叠。

我相信还有更多示例，您可以做很多很酷的事情。

Haskell - 我为什么要使用无限数据结构？

Haskell - why would I use infinite data structures?

functional-programming

lazy-evaluation