haskell - Haskell - Prime Powers Excercise - 无限合并

Question

在大学里，我的任务如下：

定义以下函数：

primepowers :: Integer -> [Integer]

它计算给定参数 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

虽然您可能无法将它用于您的作业，但可以使用 Hackage 的primes和data-ordlist包非常优雅地解决这个问题。

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 2

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

由于列表的数量是无限的，因此这是一个无限循环。

---

我建议转置结构，例如：

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

Answer 3

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

Answer 4

您需要以下功能：

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