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)

我认为它们是独立工作的,因为我已经测试了一些样本输入.合并将两个有序列表合并为一个有序列表素数返回无限列表的素数幂计算n的幂次数(即num ^ 1,num ^ 2 ... num ^ n)

我尝试合并primepowers中的所有内容,但是函数没有被评估,没有任何事情发生,分别是某种无限循环.

我对素数或权力的优化不感兴趣.只是我不明白为什么这不起作用.或者我的方法不好,不是功能,不是哈斯克尔？

Answer 1

我怀疑问题是: primes是一个无限的列表.因此,map (powers n) primes是(有限)列表的无限列表.当你foldr merge []一起尝试它们时,merge必须评估每个列表的头部......

由于列表数量无限,因此这是一个无限循环.

我建议调换结构,如:

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

Answer 2

虽然你可能不会将它用于你的任务,但是使用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]