2

http://www.haskell.org/haskellwiki/Testing_primalityから、次のコードがあります。

isPrime n = n > 1 &&
    foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes

primes は素数のリストです (おそらく無限)。

2 つの質問:

  1. foldr関数に渡されたラムダをどのように読み取るか
  2. 右から始まるのでfoldr、素数の無限リストが渡されたときにこの関数が機能するのはなぜですか? ラムダに短絡が組み込まれていると思いますか？
4

3 に答える 3

4

遅延評価は、論理が関数内にある場合でも、ブール型の短絡論理が評価される関数のチェーンを停止することを意味します。

簡単な例として、 Foldable データ型に対して、次のnullような関数を書くことができます:

null t = foldr (\x b -> False && b) True t

この関数は複数回呼び出されることはありません。複数の要素を持つインスタンスの場合、この関数は次のように評価されるためです。

False && *thunk* foldr...

短絡ブール値andは、サンクが評価されないことを意味するため、これは無限の構造でうまく機能します。nullこれが、チェックとして実装してはならない理由ですsize == 0

これは厳密な言語では機能しません。folderr の各反復は順番に評価され、次の反復に渡されます。

ラムダについては...

isPrime n = n > 1 &&
    foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes

次のように記述できます。

isPrime n = n > 1 &&
    foldr f True primes
    where
        f p r = p*p > n || ((n `rem` p) /= 0 && r)

それが役立つことを願っています。

編集: 明確でない場合、短絡ブール値または ||その関数内は、上記のより単純な例と同じように機能します。

于 2013-10-21T10:26:16.960 に答える
1

折り目は視覚的に把握しやすいかもしれません:

   foldr g z [a,b,c...,x] === g a (g b (g c (g ... (g x z) ... )))

したがってg p r、2 番目の引数を使用しない場合、それ以上のリスト アクセスは強制されません。||あなたが言ったように、 （「論理和」）の短絡動作のためです。

そしてfoldl g z [a,b,c...,x] === (g ... (g (g (g z a) b) c) ... x)。

関数を読むには、最初に、折りたたみが素数のリスト に適用されていることに気付き[2,3,5,7,11,13,17..]ます。したがって、次のように読むことができます

isPrime n = n > 1 &&
   foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes
===
isPrime n = n > 1 &&
   (2*2 > n || (rem n 2 /= 0 &&
   (3*3 > n || (rem n 3 /= 0 &&
   (5*5 > n || (rem n 5 /= 0 && 
   -- the expansion stops when p*p > n
   -- because (True || r) === True
   ......................... && 
   (True) ... ))))))

の結合関数ではfoldr、2 番目の引数はリストの残りを折りたたんだ「結果」です。rその意味で示唆に富んだ名前です。

于 2013-10-21T19:58:35.963 に答える