哈斯克尔 - 总理权力锻炼; Tibial - 无限合并

在大学里我的任务是：哈斯克尔 - 总理权力锻炼; Tibial - 无限合并

定义下列功能：
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)

我认为他们独立工作，因为我有一些样品输入测试。合并合并两个有序列表，以一个有序列表素数的回报素数的无限名单权力计算NUM正的权力（即NUM^1，NUM^2 ... NUM^N）

我尝试合并一切都在primepowers中，但函数没有被评估，没有发生任何分别的一些无限循环。

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

来源

2011-11-04 niklas

问题陈述自相矛盾。 “前n个素数的无限权力列表”和“{p^i | p是素数，1≤i≤n}“是完全不同的。 –

你好。我纠正了它。这是一个翻译错误 – niklas

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

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

我建议调换结构是这样的：

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

来源

2011-11-04 23:55:41 comingstorm

为什么你的程序运行到一个无限循环的原因是，你正试图合并无限多只列出使用不变量每个列表按升序排列。在程序输出“2”之前，它必须知道没有一个列表包含小于2的任何东西。这是不可能的，因为有无数个列表。

来源

2011-11-04 23:56:54

尽管您可能不会将它用于您的任务，但可以使用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]

来源

2011-11-05 00:12:44 hammar

感谢您的指针。我无法计算我重新实施了'mergeAll'多少次。 –

这并不重要，但如果你需要大量素数，[NumberSieves]（http://hackage.haskell.org/packages/archive/NumberSieves/0.1.1/doc/html/Math-Sieve -ONeill.html），特别是（无耻插件）[arithmoi]（http://hackage.haskell.org/package/arithmoi）使用更少的内存提供更快的筛分。 –

@DanielFischer：太棒了！我必须更仔细地检查这些。 – hammar

您需要以下功能：

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

来源

2011-11-05 01:54:40 Rotsor

哈斯克尔 - 总理权力锻炼; Tibial - 无限合并

回答

相关问题