Haskell - 列出无限列表的理解-Java 学习之路

这是一段代码

primepowers n = foldr merge [] [ map (^i) primes | i <- [1..n] ]  -- (1)

merge::(Ord t) =>[t]->[t]->[t]
merge x [] = x
merge [] y = y
merge (x:xs) (y:ys)
    | x < y = x:merge xs (y:ys)
    | otherwise = y:merge (x:xs) ys

这等于数学表达式 {p^i | p is prime, 1 <= i <= n} .

prime 返回无限的素数列表 . 我感兴趣的是 (1) 的评估 . 这些是我的想法：

如果我们首先看一下 [ map (^i) primes | i <- [1..3] ] ，这将返回 [[2,3,5,7,9,...],...] 的无限列表 . 但正如我们所知 p^1 （p是素数）永远不会结束，Haskell永远不会评估 [p^2] 和 [p^3] . 这只是因为它是一个无限的列表还是因为懒惰的评估？

让我们继续进行合并：合并将返回 [2,3,5,7,9,11,...] 因为我们仍然有一个无限的列表或者由于其他原因？

现在 foldr ： foldr 从后面开始评估 . 这里特别要求最右边的元素，这是一个无限的列表 [p^3] . 所以评估就是这样的

merge (merge (merge [] [p^3]) [p^2]) [p^1]

但是我们不应该忘记这些列表是无限的，那么Haskell如何处理这个事实呢？

谁能解释一下上述功能的评估过程？

4 回答

1

合并的列表是无限的，但这并不重要 .

重要的是您只合并了有限数量的列表，因此要计算合并的下一个元素，您只需执行有限数量的比较 .

要计算 merge xs ys 的头部，您只需要计算 xs 的头部和 ys 的头部 . 因此，通过归纳，如果您有一个有限的 merge 操作树，则可以在有限时间内计算整体合并的头部 .

回复于 2024-04-26T18:00:57+08:00
3
诀窍是将其定义为
```
primepowers n = foldr (\(x:xs) r-> x:merge xs r) 
                      [] [ map (^i) primes | i <- [1..n] ]
```
（正如Richard Bird在O'Neill，Melissa E.，“真正的Eratosthenes筛子”一文中的代码所示） .

当前列表右侧的列表都以较大的数字开头，它们的合并列表不可能产生小于或等于当前列表头部的值，因此可以无条件地生成 .

这样，它也将根据需要探索尽可能多的内部流：
```
GHCi> let pps_list = [ map (^i) primes | i <- [1..42] ]
GHCi> :sprint pps_list
pps_list = _
GHCi> take 20 $ foldr (\(x:xs) r-> x:merge xs r) [] pps_list
[2,3,4,5,7,8,9,11,13,16,17,19,23,25,27,29,31,32,37,41]
GHCi> :sprint pps_list
pps_list = (2 : 3 : 5 : 7 : 11 : 13 : 17 : 19 : 23 : 29 : 31 : 37 :
            41 : _) :
           (4 : 9 : 25 : 49 : _) : (8 : 27 : 125 : _) : (16 : 81 : _) :
           (32 : 243 : _) : (64 : _) : _
```
对于你自己的问题， foldr f z [a,b,c,...,n] = f a (f b (f c (... (f n z)...))) so（为 map (^n) primes 写 ps_n ），你的表达相当于
```
merge ps (merge ps_2 (merge ps_3 (... (merge ps_n [])...)))
= merge ps r
     where r = merge ps_2 (merge ps_3 (... (merge ps_n [])...))
```
因为您使用 merge 作为组合功能 . 请注意，最左边的 merge 首先进入操作，而 r 的表达式仍然需要--Haskell的评估是需要的 . ）

现在，这个 merge 要求它的第一个和第二个参数的头部值（如果写的话，它实际上首先检查第二个参数，因为它是 [] ） .

第一个参数不是问题，但第二个参数是折叠所有其余列表的结果（ foldr 的 foldr 的组合函数代表"recursive result"） . 因此，将访问列表中的每个元素并强制其head元素 - 所有这些只是为了产生一个非常第一个值，结果列表的头部，由最左边的 merge 调用...

在我的代码中，组合函数首先不要求其第二个参数列表的头部 . 这就是限制其对整个列表清单的探索，使其在需求中更加经济，从而提高效率（如果你完全省略 n ，它甚至会起作用） .

您的示例Haskell表达式 [ map (^i) primes | i <- [1..3] ] 返回长度为3的有限列表，每个元素都是无限列表： [[2,3,5,7,11,...],[4,9,25,...],[8,27,125,...]] 所以 foldr 没有问题将其转换为 merge [2,3,5,7,11,...] (merge [4,9,25,...] (merge [8,27,125,..] [])) ：

foldr merge [] [map（^ i）primes |我< - [1..3]] =合并[2,3,5,7,11，...]（foldr merge [] [map（^ i）primes | i < - [2..3]] ）= merge [2,3,5,7,11，...]（merge [4,9,25，...]（foldr merge [] [map（^ i）primes | i < - [3 . .3]]））= merge [2,3,5,7,11，...]（merge [4,9,25，...]（merge [8,27,125，..]（foldr merge [ ] []）））= merge [2,3,5,7,11，...]（merge [4,9,25，...]（merge [8,27,125，..] []）） = merge [2,3,5,7,11，...]（merge [4,9,25，...] [8,27,125，..]）= merge [2,3,5,7， 11，...]（4：合并[9,25，...] [8,27,125，..]）= 2：合并[3,5,7,11，...]（4：合并[ 9,25，...] [8,27,125，..]）= 2：3：合并[5,7,11，...]（4：合并[9,25，...] [8， 27,125，..]）= 2：3：4：合并[5,7,11，...]（合并[9,25，...] [8,27,125，..]）= 2：3： 4：merge [5,7,11，...]（8：merge [9,25，...] [27,125，..]）= 2：3：4：5：merge [7,11， . ..]（8：合并[9,25，...] [27,125，..]）.....

如您所见，首先检查最右边的内部列表，因为 merge 严格（即要求知道）它的两个参数，如上所述 . 对于 [ map (^i) primes | i <- [1..42] ] ，它会扩展其中的所有42个，并在生成结果的头部元素之前检查所有这些头部 .

使用调整函数 mg (x:xs) r = x:merge xs r ，评估继续执行

foldr mg [] [map（^ i）primes |我< - [1..3]] = mg [2,3,5,7,11，...]（foldr mg [] [map（^ i）primes | i < - [2..3]] ）= 2：合并[3,5,7,11，...]（foldr mg [] [map（^ i）primes | i < - [2..3]]）= 2：merge [3,5 ，7,11，...]（mg [4,9,25，...]（foldr mg [] [map（^ i）primes | i < - [3..3]]））= 2：合并[3,5,7,11，...]（4：合并[9,25，...]（foldr mg [] [map（^ i）primes | i < - [3..3]] ））= 2：3：合并[5,7,11，...]（4：合并[9,25，...]（foldr mg [][map（^ i）primes |我< - [3..3]]））= 2：3：4：合并[5,7,11，...]（合并[9,25，...]（foldr mg [] [map（ ^ i）素数| i < - [3..3]]））= 2：3：4：合并[5,7,11，...]（合并[9,25，...]（mg [ 8,27,125，..]（foldr mg [] []）））= 2：3：4：合并[5,7,11，...]（合并[9,25，...]（8：合并[27,125，..]（foldr mg [] []）））= 2：3：4：合并[5,7,11，...]（8：合并[9,25，...]（合并[27,125，..]（foldr mg [] []）））= 2：3：4：5：合并[7,11，...]（8：合并[9,25，...]（合并[27,125，..]（foldr mg [] []）））.....

所以它开始更快地产生结果，而不扩展大部分内部列表 . 这只是 foldr 的定义，
```
foldr f z (x:xs) = f x (foldr f z xs)
```
其中，由于懒惰，如果 f 不要求其值（或其一部分，如其头部），则不会立即评估 (foldr f z xs) .
回复于 2024-04-26T18:00:57+08:00
1
确实 merge 需要完全扫描其整个输入列表以产生其整个输出 . 但是，关键点在于输出中的每个元素仅取决于输入列表的有限前缀 .

例如，考虑 take 10 (map (*2) [1..]) . 要计算前10个元素，您不需要检查整个 [1..] . 实际上， map 不会扫描整个无限列表并且"after that"开始返回输出：如果它表现得那样，它就会挂在无限列表上 . map 的"streaming"属性由懒惰和 map 定义给出
```
map f [] = []
map f (x:xs) = x : map f xs
```
最后一行读取“yield x，然后继续其余”，因此调用者在 map 产生其整个输出之前检查 x . 通过比较
```
map f xs = go xs []
  where go []     acc = acc
        go (x:xs) acc = go xs (acc ++ [f x])
```
将是 map 的另一个定义，它将在其输入被消耗后才开始生成其输出 . 它等同于有限列表（性能除外），但不等同于无限列表（挂在无限列表上） .

如果你想凭经验测试你的 merge 确实懒得工作，试试这个：
```
take 10 $ merge (10:20:30:error "end of 1") (5:15:25:35:error "end of 2")
```
通过改变常数随意玩 . 您将看到屏幕上打印的异常，但只有在 merge 已经生成了一些列表元素之后 .
回复于 2024-04-26T18:00:57+08:00
2
[map (^i) primes | i <- [1..3]] 只返回 thunk . 现在没有评估任何东西 . 你可以试试这个：
```
xs = [x | x <- [1..], error ""]

main = print $ const 0 xs
```
此程序打印 0 ，因此此处未评估 error "" .

您可以考虑 foldr 定义如下：
```
foldr f z  []    = z
foldr f z (x:xs) = f x (foldr f xs)
```
然后
```
primepowers n = foldr merge [] [map (^i) primes | i <- [1..3]]
```
像这样评估（强制之后）：
```
merge thunk1 (merge thunk2 (merge thunk3 []))
```
其中 thunkn 是第n次幂中素数的暂停计算 . 现在第一个 merge 力评估 thunk1 和 merge thunk2 (merge thunk3 []) ，它们被评估为弱头正常形式（whnf） . 强制 merge thunk2 (merge thunk3 []) 导致强制 thunk2 和 merge thunk3 [] . merge thunk3 [] 缩减为 thunk3 然后强制 thunk3 . 所以表达成了
```
merge (2 : thunk1') (merge (4 : thunk2') (8 : thunk3'))
```
其中，由于合并的定义，减少到
```
merge (2 : thunk1') (4 : merge thunk2' (8 : thunk3')
```
然后再次：
```
2 : merge thunk1' (4 : merge thunk2' (8 : thunk3')
```
现在 merge 强制 thunk1' ，但不是表达的其余部分，因为它已经在whnf
```
2 : merge (3 : thunk1'') (4 : merge thunk2' (8 : thunk3)
2 : 3 : merge thunk1'' (4 : merge thunk2' (8 : thunk3')
2 : 3 : merge (5 : thunk1''') (4 : merge thunk2' (8 : thunk3')
2 : 3 : 4 : merge (5 : thunk1''') (merge thunk2' (8 : thunk3')
2 : 3 : 4 : merge (5 : thunk1''') (merge (9 : thunk2'') (8 : thunk3')
2 : 3 : 4 : merge (5 : thunk1''') (8 : merge (9 : thunk2'') thunk3')
2 : 3 : 4 : 5 : merge thunk1''' (8 : merge (9 : thunk2'') thunk3')
...
```
直观地，只需要评估那些值 . 阅读this以获得更好的解释 .

您还可以合并无限列表的无限列表 . 最简单的方法是：
```
interleave (x:xs) ys = x : interleave ys xs

primepowers = foldr1 interleave [map (^i) primes | i <- [1..]]
```
interleave 函数交错两个无限列表，例如， interleave [1,3..] [2,4..] 等于 [1..] . 所以 take 20 primepowers 给你 [2,4,3,8,5,9,7,16,11,25,13,27,17,49,19,32,23,121,29,125] . 但是这个列表是无序的，我们可以做得更好 .

[map (^i) primes | i <- [1..]] 减少到
```
[[2,3,5...]
,[4,9,25...]
,[8,27,125...]
...
]
```
我们有前提条件，即在每个第n个列表中都有比第（n 1）个列表的头部更小的元素 . 我们可以从第一个列表中提取这些元素（ 2 和 3 小于 4 ），现在我们有了这个：
```
[[5,7,11...]
,[4,9,25...]
,[8,27,125...]
...
]
```
前提条件不成立，所以我们必须解决这个问题并交换第一个列表和第二个列表：
```
[[4,9,25...]
,[5,7,11...]
,[8,27,125...]
...
]
```
现在我们提取 4 并交换第一个列表和第二个列表：
```
[[5,7,11...]
,[9,25,49...]
,[8,27,125...]
...
]
```
但前提条件不成立，因为第二个列表中的元素（ 9 ）不小于第三个列表的头部（ 8 ） . 所以我们再次做同样的伎俩：
```
[[5,7,11...]
,[8,27,125...]
,[9,25,49...]
...
]
```
现在我们可以再次提取元素 . 无限重复这个过程给了我们有序的主要权力列表 . 这是代码：
```
swap xs@(x:_) xss = xss1 ++ xs : xss2 where
    (xss1, xss2) = span ((< x) . head) xss 

mergeAll (xs:xss@((x:_):_)) = xs1 ++ mergeAll (swap xs2 xss) where
    (xs1, xs2) = span (< x) xs

primepowers = mergeAll [map (^i) primes | i <- [1..]]
```
例如， take 20 primepowers 等于 [2,3,4,5,7,8,9,11,13,16,17,19,23,25,27,29,31,32,37,41] .

这可能不是获得有序素数列表的最好方法，但它很容易 .

EDIT

查看 Will Ness '答案以获得更好的解决方案，这既简单又好 .
回复于 2024-04-26T18:00:57+08:00

Haskell - 列出无限列表的理解

4 回答

相关问题