22

このコードのチャンクを理解するのに苦労しています:

let
  sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)
in sieve [2 .. ]

誰かが私のためにそれを分解できますか? 再帰があることは理解していますが、それがこの例の再帰がどのように機能するかを理解できない問題です。

4

5 に答える 5

24

ここで他の人が述べたこととは反対に、この関数はEratosthenesの真のふるいを実装していません。ただし、素数の最初のシーケンスが返され、同様の方法で返されるため、エラトステネスのふるいと考えても問題ありません。

mipadiが彼の答えを投稿したとき、私はコードの説明を終えようとしていました。削除することもできますが、時間をかけて作成したため、回答が完全に同じではないため、ここに残しておきます。

まず、投稿したコードにいくつかの構文エラーがあることに注意してください。正しいコードは、

let sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs) in sieve [2..]

  1. let x in yを定義xし、その定義を で使用できるようにしyます。この式の結果は の結果ですy。したがって、この場合、関数を定義し、に適用しsieveた結果を返します。[2..]sieve

  2. letここで、この式の部分を詳しく見てみましょう。

    sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs)
    1. sieveこれは、リストを最初の引数として受け取る関数を定義します。
    2. (p:xs)上記のリストの先頭と末尾 (先頭以外のすべて)に一致するパターンです。pxs
    3. 一般に、p : xs最初の要素が であるリストですp。xs残りの要素を含むリストです。したがって、sieve受け取ったリストの最初の要素を返します。

    4. リストの残りの部分は見ていません:

      sieve (filter (\x -> x `mod` p /= 0) xs)
      1. sieveが再帰的に呼び出されていることがわかります。したがって、filter式はリストを返します。
      2. filterフィルター関数とリストを取ります。フィルター関数が true を返すリスト内の要素のみを返します。

      3. この場合xs、リストはフィルタリングされ、

        (\x -> x `mod` p /= 0)

        フィルター機能です。

      4. filter 関数は引数を 1 つ取り、xの倍数でない場合は true を返しますp。

  3. sieveが定義されたので、2 から始まるすべての自然数のリストである を渡します。[2 .. ]したがって、

    1. 数値 2 が返されます。2 の倍数である他のすべての自然数は破棄されます。
    2. したがって、2 番目の数値は 3 です。これが返されます。他のすべての 3 の倍数は破棄されます。
    3. したがって、次の数は 5 になります。
于 2009-11-19T15:50:19.137 に答える
17

それは実際にはかなりエレガントです。

まず、sieve要素のリストを取る関数を定義します。

sieve (p:xs) =

の本体でsieveは、リストの先頭を取得し (無限の list を渡し、 2 が素数であると定義されているため) 、残りのリスト[2..]に適用した結果に (遅延して!) 追加します。sieve

p : sieve (filter (\ x -> x 'mod' p /= 0) xs)

それでは、リストの残りの作業を行うコードを見てみましょう。

sieve (filter (\ x -> x 'mod' p /= 0) xs)

sieveフィルタリングされたリストに適用しています。フィルター部分の機能を分解してみましょう。

filter (\ x -> x 'mod' p /= 0) xs

filter関数とその関数を適用するリストを取り、関数によって与えられた基準を満たす要素を保持します。この場合、filter無名関数を取ります:

\ x -> x 'mod' p /= 0

この無名関数は 1 つの引数を取りますx。のモジュラスをチェックしますx（pリストの先頭、呼び出されるたびにsieve）：

 x 'mod' p

モジュラスが 0 でない場合:

 x 'mod' p /= 0

その後、要素xはリストに保持されます。0 の場合は除外されます。これは理にかなっています:xが で割り切れる場合、 はp1xとそれ自体だけで割り切れるので、素数ではありません。

于 2009-11-19T15:49:13.710 に答える
10

ジェネレーターを定義します- 「ふるい」と呼ばれるストリームトランスフォーマー、

Sieve s = 
  while( True ):
      p := s.head
      s := s.tail
      yield p                             -- produce this
      s := Filter (nomultsof p) s         -- go next

primes := Sieve (Nums 2)

と同等の無名関数のカリー化された形式を使用します

nomultsof p x = (mod x p) /= 0

Sieveとは両方とも、Filter内部状態と値渡し引数のセマンティクスを使用したデータ構築操作です。

ここで、このコードの最も明白な問題は ではないことがわかります。繰り返しますが、試行除算を使用して作業シーケンスから倍数を除外しますが、 の増分でカウントアップすることpにより、それらを直接見つけることができます。前者を後者に置き換えたとしても、結果として得られるコードの実行時間は依然として非常に複雑になります。

いいえ、その最も明白な問題は、素数の二乗が入力に見られた後にのみ実際にそれを行うべきなのにFilter、作業シーケンスの上にあまりにも早く置くことです。その結果、実際に必要なものと比較して s の二次数が作成されます。それが作成する一連のs が長すぎて、それらのほとんどはまったく必要ありません。FilterFilter

適切な瞬間までフィルタの作成を延期した修正版は、次のとおりです。

Sieve ps s = 
  while( True ):
      x := s.head
      s := s.tail
      yield x                             -- produce this
      p := ps.head
      q := p*p
      while( (s.head) < q ):
          yield (s.head)                  --    and these
          s := s.tail
      ps := ps.tail                       -- go next
      s  := Filter (nomultsof p) s

primes := Sieve primes (Nums 2)

またはHaskellでは、

primes = sieve primes [2..] 
sieve ps (x:xs) = x : h ++ sieve pt [x | x <- t, rem x p /= 0]
     where (p:pt) = ps
           (h,t)  = span (< p*p) xs

rem一部のインタープリターでははるかに高速になる可能性があるため、代わりにここで使用されmodます。とにかく、数値はすべて正です。

問題サイズのポイント で実行時間をとることにより、アルゴリズムの局所的な成長次数を測定します。t1,t2n1,n2logBase (n2/n1) (t2/t1)O(n^2)O(n^1.4)n

明確にするために、欠落している部分はこの (架空の) 言語で次のように単純に定義できます。

Nums x =            -- numbers from x
  while( True ):
      yield x
      x := x+1

Filter pred s =     -- filter a stream by a predicate
  while( True ):
      if pred (s.head) then yield (s.head)
      s := s.tail

も参照してください。

更新:興味深いことに、AJT Davie の 1992 年の Haskell の本によると、David Turner の 1976 年の SASL マニュアルでこのコードの最初のインスタンスが、

    primes = sieve [2..]

    sieve (p:nos) = p : sieve (remove (multsof p) nos)

実際には、この質問のような試行除算ふるいのための 1 つのペアと、エラトステネスの本物のふるいとしても知られる、カウントによって直接生成された各素数の倍数の順序付けられた除去のための2 つの ペアの実装をremove認めています (両方とももちろん延期はありません）。ハスケルでは、multsof

    multsof p n = (rem n p)==0              multsof p = [p*p, p*p+p..]

    remove m xs = filter (not.m) xs         remove m xs = minus xs m

(彼がここで実際の実装を選択するのを延期していれば...)

延期されたコードに関しては、「リストパターン」を使用した擬似コードでは、

    primes = [2, ...sieve primes [3..]]

    sieve [p, ...ps] [...h, p*p, ...nos] =
                     [...h, ...sieve ps (remove (multsof p) nos)]

ViewPatterns現代のHaskellでは次のように書くことができます

{-# LANGUAGE ViewPatterns #-}

primes = 2 : sieve primes [3..]

sieve (p:ps) (span (< p*p) -> (h, _p2 : nos)) 
                             = h ++ sieve ps (remove (multsof p) nos)
于 2012-01-15T17:51:54.497 に答える
2

エラトステネスのふるいを実装しています

基本的に、素数 (2) から始めて、残りの整数 (すべて 2 の倍数) から除外します。そのフィルタリングされたリストの次の数値も素数でなければならないため、残りの倍数からすべての倍数をフィルタリングします。

于 2009-11-19T15:42:14.533 に答える
2

「一部のリストのふるいは、リストの最初の要素 (p と呼びます) であり、p で割り切れない要素のみが通過できるようにフィルター処理されたリストの残りのふるいです」。次に、2 から無限大までのすべての整数のふるいを返すことから始めます (2 の後に 2 で割り切れないすべての整数のふるいが続きます)。

Haskell を攻撃する前にThe Little Schemerをお勧めします。

于 2009-11-19T15:47:43.087 に答える