哈斯克爾 - 總理權力鍛鍊; 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 - 無限合併

回答

相關問題