1

Haskell でハミング数を生成しようとしています。問題は、出力リストに重複した # が表示され、その理由が正確にわからないことです。重複削除機能を作成するだけですか、それとも単純なものが不足していますか?

また、関数 hamming では、入力リストのサイズが正確に 3 であることを確認したいのですが、リストのサイズを見つけて比較を行うにはどうすればよいですか?

{- Merge lists x&y of possibly infinite lengths -}
merge [] [] = []
merge [] ys = ys
merge xs [] = xs
merge xs ys = min x y : if x < y then merge (tail xs) ys
                             else merge xs (tail ys)
    where x = head xs
          y = head ys

{- multiply each element in y by x -}
times x [] = []
times x y = x * (head y) : times x (tail y)

{- find the hamming numbers of the input primes list -}
ham [] = []
ham x = 1 : merge (times (head x) (ham x))
             (merge (times (x !! 1) (ham x)) (times (last x) (ham x)))

{- returns x hamming #'s based on y primes of size 3 -}
hamming x [] = []
hamming x y = take x (ham y) 
{- hamming x y = if "y.size = 3" then take x (ham y) 
                                 else "Must supply 3 primes in input list" -}
4

2 に答える 2

2

ハミング数の多くはいくつかの基数の倍数であり、関数内の重複を削除しないため、重複が発生しますmerge。たとえば、古典的な2, 3, 5ハミング数の場合、6と。を取得2 * 3し3 * 2ます。

もちろん、重複する削除関数を作成することもできます。作成するリストはソートされているので、それはそれほど非効率的ではありません。または、マージ関数で重複を削除することもできます。

比較できるようにリストのサイズを見つけるにはどうすればよいですか？

リストの長さは、lengthから使用できる関数を使用して取得できますが、リスト全体をトラバースして長さを計算する必要があるためPrelude、呼び出しlengthは本当に長さが必要な場合にのみ実行する必要があることに注意してください。lengthリストがたまたま長い場合、それには多くの時間がかかり、リストが他の場所で参照されてガベージコレクションされない場合、大量のメモリ使用量が発生する可能性があります。リストが無限であっても、その長さの評価はもちろん終了しません。

あなたがやりたいことは、パターンマッチングによっても達成できます。

ham [a, b, c] = list
  where
    list = 1 : merge (map (a*) list) (merge (map (b*) list) (map (c*) list))
ham _ = []

lengthチェック付きのガードを使用することもできます

hamming x y
    | length y == 3 = take x (ham y)
    | otherwise     = []

入力リストに正確に3つの要素が含まれていることを確認しますが、を呼び出すと後悔しますhamming 10 [1 .. ]。

于 2012-07-27T19:51:37.537 に答える
1

Listモジュールには、Haskell には という重複リムーバーがありますnub。これは hoogle にあります: http://www.haskell.org/hoogle/?hoogle=nub。ただし、これは O(n^2) であるため、 を変更した方がよい場合がありますmerge。ただし、最適化する前に、既に作成されている遅いソリューションを最初に使用することをお勧めします。

あなたはこのちょっとした演習で Haskell を学ぼうとしていると思いますが、 List モナドを使ってハミング数を書き出す別の方法があります (重複はありませんが、順序どおりではありません) :

uglyNumbers = do { n <- [0..] 
                 ; k <- [0..n] 
                 ; j <- [0..n-k] 
                 ; return $ (2^(n-k-j))*(3^j)*(5^k) }

これにより、ハミング数の怠惰な無限リストが作成されます。これは、リスト内包表記を使用して同等に記述できます。

uglyNumbers' = [(2^(n-k-j))*(3^j)*(5^k) | n <- [0..], k <- [0..n], j <- [0..n-k]]
于 2012-07-28T03:27:24.843 に答える