Haskell中,可以这样定义无限列表:
[1.. ]
我找到了许多有关如何实现无限列表的文章,我也理解了它的工作原理。然而,我无法想出使用无限数据结构概念的任何理由。
有人能给我举一个在Haskell中可以更轻松地(或仅能)使用无限列表解决的问题的例子吗?
Haskell中,可以这样定义无限列表:
[1.. ]
我找到了许多有关如何实现无限列表的文章,我也理解了它的工作原理。然而,我无法想出使用无限数据结构概念的任何理由。
有人能给我举一个在Haskell中可以更轻松地(或仅能)使用无限列表解决的问题的例子吗?
total = 0;
for x in xs {
if (x < 5) {
total = total + x * 2;
}
}
这意味着性能是可组合的:由于惰性求值,在处理列表时,该代码具有恒定的内存使用量。而在map
或者filter
中并没有什么特别的东西使得这种情况发生:它们可以完全独立。
举个例子,标准库中的and
函数计算一个列表的逻辑“与”(logical AND),例如and [a, b, c] == a && b && c
,并且其实现仅仅是一个fold: and = foldr (&&) True
。一旦它到达输入中的False
元素,它就会停止求值,这仅仅是因为&&
对其右参数是惰性的。惰性给你带来了组合的能力!
关于所有这些的一篇好文章,请阅读约翰·休斯(John Hughes)著名的《为什么函数式编程很重要》,其中详细介绍了惰性函数式编程(Miranda语言的前身)的优势。
sort
的算法保证最小元素可以在线性时间内被识别出来吗(例如插入排序)? - chepnersort
是一种归并排序,由于惰性的缘故更像堆排序。如果是这样,它应该保证生成第一个元素的时间复杂度为O(n)。 - chi[5, 6, 4, 7, 3, 8, 2, 9, 1] -> [[5, 6], [4, 7], [3, 8], [2, 9], [1]] -> [[4,5,6,7],[2,3,8,9],[1]] -> [[2,3,4,5,6,7,8,9],[1]] -> [[1,2,3,4,5,6,7,8,9]] -> [1,2,3,4,5,6,7,8,9]
。在完成中间的合并步骤之前,无法提取头项。 - chepnerAnnotating a list with its indices temporarily uses an infinite list of indices:
zip [0..] ['a','b','c','d'] = [(0,'a'), (1,'b'), (2,'c'), (3,'d')]
Memoizing functions while maintaining purity (in this case this transformation causes an exponential speed increase, because the memo table is used recursively):
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)
Purely mocking programs with side-effects (free monads)
data IO a = Return a
| GetChar (Char -> IO a)
| PutChar Char (IO a)
Potentially non-terminating programs are represented with infinite IO strucutres; e.g. forever (putChar 'y') = PutChar 'y' (PutChar 'y' (PutChar 'y' ...))
Tries: if you define a type approximately like the following:
data Trie a = Trie a (Trie a) (Trie a)
it can represent an infinite collection of a
s indexed by the naturals. Note that there is no base case for the recursion, so every Trie
is infinite. But the element at index n
can be accessed in log(n)
time. Which means you can do something like this (using some functions in the inttrie
library):
findIndices :: [Integer] -> Trie [Integer]
findIndices = foldr (\(i,x) -> modify x (i:)) (pure []) . zip [0..]
this builds an efficient "reverse lookup table" which given any value in the list can tell you at which indices it occurs, and it both caches results and streams information as soon as it's available:
-- 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,...
all from a one-line infinite fold.
enumerate
,它将列表中的每个元素与其索引放入元组中。这可以通过一个带有索引参数的辅助函数进行递归定义,或更简单地使用zipWith [0..]
来定义。由于 zip 的特性,编写[0..]
比编写[0.. length list - 1]
要容易得多且更一般化。 - coletake 50 fibonacci
,其中fibonacci
是通过自身来定义的。 - BergifreeIn
expression)]”是一个简短的代码,用于生成一个在“expression”中没有出现过的新名称。虽然它不太高效,但很容易编写和理解。还有类似的情况,需要在满足某些条件的无限多个值中找到“第一个”值,并且过滤无限列表非常自然。在我看来,无限树并不是很有用。 - chizip [0..]
的例子,但说实话这个例子有点浅显,因为不仅 Python 的enumerate
可以胜任这个工作,甚至在 Haskell 中也可以做到:当使用Data.Vector
时,你会使用indexed
而不是 zip。 - leftaroundabout