haskell - Haskell-素数冪エクササイズ-無限のマージ

Question

大学での私の仕事は次のとおりです。

次の関数を定義します。

primepowers :: Integer -> [Integer]

これは、与えられたパラメータnの素数の最初のn乗の無限リストを計算し、ascでソートします。つまり、primepowers nには、の要素が昇順で含まれています。

{p ^ i | pは素数、1≤i≤n}です。

このタスクに取り組んだ後、私は行き止まりになりました。私には次の4つの機能があります。

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)

いくつかのサンプル入力でテストしたので、それらは独立して機能すると思います。マージは2つの順序付きリストを1つの順序付きリストにマージします素数は素数の無限リストを返します累乗はnumのn乗を計算します（つまり、num ^ 1、num ^ 2 ... num ^ n）

私はすべてをprimepowersでマージしようとしますが、関数は評価されません。それぞれ、ある種の無限ループが発生します。

素数や累乗の最適化には興味がありません。なぜそれがうまくいかないのか分かりません。それとも、私のアプローチは良くなく、機能的でもなく、haskellでもありませんか？

Answer 1

問題は次のとおりだと思い primesます。は無限のリストです。したがって、map (powers n) primesは（有限）リストの無限リストです。foldr merge []それらをすべて一緒にしようとするときmergeは、各リストの先頭を評価する必要があります...

リストの数は無限であるため、これは無限ループです。

---

次のような構造を転置することをお勧めします。

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

Answer 2

おそらくこれを割り当てに使用することはできませんが、Hackageの素数とデータ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 3

プログラムが無限ループに陥る理由は、各リストが昇順でソートされる不変条件を使用するだけで、無限に多くのリストをマージしようとしているためです。プログラムが「2」を出力する前に、どのリストにも2より小さいものが含まれていないことを知っておく必要があります。これは、リストが無限にあるため不可能です。

Answer 4

次の関数が必要です。

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