5

私の特定の問題は、foldl出力の終了または生成を妨げていますか?

最初に、素数のふるいを達成しました。それは最高ではありませんが、（たとえば）のようにうまく機能しtake 20 primesAます。

primesA :: [Integer]
primesA = sieve 2 []

sieve :: Integral a => a -> [a] -> [a]
sieve i []   = (i:) $ sieve (i + 1) $ map (*i) [i ..]
sieve i composites@(h : t)
  | i == h    =     sieve (i + 1) t
  | otherwise = (i:) $ sieve (i + 1) $ unionIncreasing composites $ map (*i) [i ..]

unionIncreasing :: Ord a => [a] -> [a] -> [a]
unionIncreasing [] b = b
unionIncreasing a [] = a
unionIncreasing a@(ah:at) b@(bh:bt) | ah <  bh  = ah : at `unionIncreasing` b
                                    | ah == bh  = ah : at `unionIncreasing` bt
                                    | otherwise = bh : a  `unionIncreasing` bt

i次に、次のように使用してカウンターを削除する方が Haskell-y であると考えましたfoldl。しかし、これは効果的ではありません。

primesB :: [Integer]
primesB = [2..] `differenceIncreasing` composites

composites :: [Integer]
composites = foldl f [] [2..]
  where f [] i = map (*i) [i ..]
        f knownComposites@(h:t) i | i == h    = knownComposites
                                  | otherwise = (h:) $ unionIncreasing t $ map (*i) [i ..]

differenceIncreasing :: Ord a => [a] -> [a] -> [a]
differenceIncreasing [] b = []
differenceIncreasing a [] = a
differenceIncreasing (x:xs) (y:ys) | x <  y    = x : xs `differenceIncreasing` (y:ys)
                                   | x == y    = xs `differenceIncreasing` ys
                                   | otherwise = (x:xs) `differenceIncreasing` ys

(たとえば) を実行しても、終了も出力も生成されませんhead primesB。

おそらく ghci は、リストの先頭の値を取得する無駄な試みで、素数の倍数の無限に多くのリストを調べています。

しかし、なぜそれは具体的にそれを行うのですか?

4

3 に答える 3

11

foldl無限リストで終了することはできません。これは関数の定義です:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

Haskell では、サンクを強制すると、最も外側の操作がデータ コンストラクターであるステップに到達したときにのみ評価が停止することに注意してください (明示的な強制または遅延パターン マッチングを使用しない限り)。の場合はfoldl、ヒットしたときのみ可能[]です。この例を見てみましょう。無限リストを逆にします (これはすでにそれを与えているはずです):

foldl (flip (:)) [] [1..]
  = foldl (flip (:)) [1] [2..]
  = foldl (flip (:)) [2, 1] [3..]
  = foldl (flip (:)) [3, 2, 1] [4..]
  = foldl (flip (:)) [4, 3, 2, 1] [5..]
  .
  .
  .

foldlは常に最も外側の演算子でありfoldl、コンストラクターではないため、終了することはありません。よく考えてみると、無限リストの左折畳みは決して終了できないことがわかります。

foldrf2 番目の方程式が一番上にあるため、その問題はありません。

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

例：

foldr (:) [] [1..]
  = 1 : foldr (:) [] [2..]

Now(:)は最も外側の演算子なので、評価はここで停止します。評価のためのコンストラクターの引数を強制的に継続させる必要があります。

于 2013-04-29T05:28:33.370 に答える
2

(明確化: これは、https://cstheory.stackexchange.com/ でのあなたの質問に対する私の回答の最後の部分を多かれ少なかれ厳密に繰り返し、少し詳しく説明しています。それが適切かどうかはわかりません。 )

あなたの最初のバージョンは、実際には Richard Bird のソリューション (M. O'Neill の論文の 11 ページから) に非常に近いものです。試行錯誤ではなく、コードの変換と段階的な改善によってそこにたどり着くことができます。

名前を変更した後、最初のステップを事前に計算すると、次の非常に見栄えの良いコードが得られます。

--     map (*i) [i ..] == map (*i) [i, i+1 ..] == [i*i, i*i+i ..]
--     sieve 2 [] where sieve i [] = (i:) $
--               sieve (i + 1) [i*i, i*i+i ..] == 2 : sieve 3 [4, 6 ..]

primesA :: [Integer]
primesA = 2 : sieve 3 [4, 6 ..]

sieve p cs@(c : t)
   | p == c    =     sieve (p + 1) t
   | otherwise = p : sieve (p + 1) (unionI cs [p*p, p*p+p ..])

unionI a@(x:xs) b@(y:ys) | x <  y    = x : xs `unionI` b
                         | x == y    = x : xs `unionI` ys
                         | otherwise = y : a  `unionI` ys

このコードには 2 つの問題があります。(...(((a+b)+c)+d)+...)より頻繁に生成されるストリームを、より頻繁に生成されないストリームよりも下に配置する計算構造があります。

しかし、より差し迫った懸念は、各素数の倍数の時期尚早な処理です。たとえば、5 に達すると[25, 30 ..]、コンポジットに追加されます。ただし、これは 25 に達したときにのみ行う必要があります。そうすることで、各時点で処理される倍数ストリームの総数が大幅に削減されます ( n番目の素数のからΘ(n)まで)。これは、効率に非常に大きな影響を与えます。Θ(sqrt(n/log n))

生成されている素数シーケンス自体から取得した素数の二乗を明示的に同期できます (これpsは、シーケンスへの別のバックポインターを維持するだけであり、生成ポイントよりもはるかに遅いペースで進められます)。

primesAC = [2,3] ++ sieve 4 (tail primesAC) 9 [4,6..]

sieve k ps@(p:pt) q cs@(c:ct)                 -- candidate "k", prime "p"
  | k == c  =     sieve (k + 1) ps q ct       -- square "q", composite "c"
  | k < q   = k : sieve (k + 1) ps q cs
  | otherwise =   sieve k       pt (head pt^2)       -- k == q == p*p
                        (unionI cs [q, q+p ..])

これは、Richard Bird のソリューションからわずか半歩離れたところにあり、巧妙に使用された を使用して両方の問題を修正し、新しい素数の倍数ストリームがそれぞれ素数の平方から開始され、同期がデータ内で暗黙的に行われる計算構造foldrを作成します。a+(b+(c+(...)))

primesAD = (2 :) . sieve 3 . 
            foldr (\p r-> p*p : unionI [p*p+p, p*p+2*p ..] r) [] $ primesAD

sieve p cs@(c : t)                  -- == diffI [p..] cs, if p<=c
  | p == c    =     sieve (p + 1) t
  | otherwise = p : sieve (p + 1) cs

各素数の 2 乗は最初に無条件に生成され、暴走アクセスがデータのさらなる部分を時期尚早に強制するのを防ぎます。

したがってfoldr、および ではなくfoldlは、この問題に自然に適合します。

あなたの2番目のバリアントは

primesB :: [Integer]
primesB = [2..] `diffI` composites

composites = foldl f [4,6..] [3..]
  where 
        f cs@(h:t) i | i == h    = cs    
                     | otherwise = h : unionI t [i*i, i*i+i ..]

diffI (x:xs) (y:ys) | x <  y    = x : xs `diffI` (y:ys)
                    | x == y    =     xs `diffI` ys
                    | otherwise = (x:xs) `diffI` ys

compositesこれは明らかに、各数値の倍数を混合物に同様に繰り返し加算することによって計算することを意図しています。問題は、完全にfoldl終了することのない内部計算プロセスに入れないことです（他の回答がすでに指摘しているように）。そのように容赦ありません。:) これを生産的なベースの反復に変えることはできますが、時期尚早の追加と構造の反転という同じ問題が残ります。さらに、以前のように素数だけでなく、すべての数値の倍数を追加するようになりました:foldl iterate

composites = foldl f [4,6..] [3..]
 -- no part of calculation of (f [4,6..] 3) is forced here, but if it were, ...
 = foldl f (f [4,6..] 3) [4..]                  
 = foldl f (4:unionI [6,8..] [9,12..]) [4..]    
 = foldl f (4:unionI [6,8..] [9,12..]) [5..]
 = foldl f (4:union (unionI [6,8..] [9,12..]) [25,30..]) [6..]
 = foldl f (4:union (union (unionI [6,8..] [9,12..]) [25,30..]) [36,42..]) [7..]
 = ....

And ([2..] `diffI`)は上記と同じなsieve 2ので、何も追加しません。

于 2013-05-29T18:23:30.780 に答える
0

私のコードを修正する方法を疑問に思う人のためprimesBに、次のリビジョンが機能します。Klaus Draegerがここ cstheory.se に書いたように、「個々のヘッドを適切にインターリーブ」します。これは、ME O'Neill The Genuine Sieve of Eratosthenes の11ページにある Richard Bird に起因するコードと同等ですが、それほど喜ばしいものではありません。 .pdf (@Wes に感謝) として印刷: http://dx.doi.org/10.1017/S0956796808007004

primesB :: [Integer]
-- #1 necessary change
-- primesB = [2..] `differenceIncreasing` composites
primesB = 2 : [3..] `differenceIncreasing` composites

-- #2 necessary change, entire function
composites = foldr f [] primesB -- not foldl, not [2..]
  where f :: Integer -> [Integer] -> [Integer]
        -- no destructuring of knownComposites;
        -- square the first list element and don't put that in unionIncreasing's second argument
        f i knownComposites = ((i*i):) $ unionIncreasing knownComposites $ map (*i) [(i+1)..]

-- No change needed in `unionIncreasing` and `differenceIncreasing`.

試行錯誤によるものでない限り、人がこの解決策をどのように達成するかはまだわかりません.

于 2013-05-05T02:46:29.960 に答える