Haskell - Prime Powers 练习 - 无限合并

Question

在大学我的任务是：

定义以下函数：

primepowers :: 整数 -> [整数]

计算给定参数 n 的素数前 n 次幂的无限列表，按 asc 排序。 那是， primepowers n 按升序包含 的元素

{p^i | p 是质数，1≤i≤n}。

在完成这项任务后，我陷入了死胡同。我有以下四个功能：

merge :: Ord t => [t] -> [t] -> [t]
merge [] b = b
merge a [] = a
merge (a:ax) (b:bx)
  | a <= b    = a : merge ax (b:bx)
  | otherwise = b : merge (a:ax) bx

primes :: [Integer] 
primes = sieve [2..]
    where sieve [] = []
          sieve (p:xs) = p : sieve (filter (not . multipleOf p) xs)
            where multipleOf p x = x `mod` p == 0   

powers :: Integer -> Integer -> [Integer] 
powers n num = map (\a -> num ^ a) [1..n]

primepowers :: Integer -> [Integer]
primepowers n = foldr merge [] (map (powers n) primes)

我认为它们独立工作，因为我已经使用一些示例输入进行了测试。 merge 将两个有序列表合并为一个有序列表 primes 返回无限的素数列表 powers 计算 num 的 n 次方（即 num^1 、 num^2 ... num^n ）

我尝试合并 primepowers 中的所有内容，但函数未进行评估，没有任何反应，分别存在某种无限循环。

我对素数或幂的优化不感兴趣。只是我不明白为什么这不起作用。或者我的方法不好，不实用，不是haskell？

Answer 1

我怀疑问题是：primes 是一个无限列表。因此，map (n) primes 是（有限）列表的无限列表。当您尝试foldr merge []它们全部在一起时，merge必须评估每个列表的头部...

由于列表的数量是无限的，所以这是一个无限环形。

---

我建议转换结构，例如：

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

Answer 2

虽然您可能无法将其用于您的作业，但可以使用 素数和数据-ordlist来自 Hackage 的软件包。

import Data.List.Ordered
import Data.Numbers.Primes

primePowers n = mergeAll [[p^k | k <- [1..n]] | p <- primes]

请注意，mergeAll 能够合并无限数量的列表，因为它假定除了列表本身已排序之外，列表的头部也是有序的。因此，我们也可以轻松地使其适用于无限幂：

allPrimePowers = mergeAll [[p^k | k <- [1..]] | p <- primes]

Answer 3

您的程序陷入无限循环的原因是您试图仅通过使用每个列表按升序排序的不变量来合并无限多个列表。在程序可以输出“2”之前，它必须知道没有一个列表包含小于 2 的任何值。这是不可能的，因为列表有无限多个。

Answer 4

您需要以下功能：

mergePrio (h : l) r = h : merge l r