解釋這段輸出素數流的haskell代碼我很難理解這段代碼：let
sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)in sieve [2 .. ]有人可以為我分解嗎？我知道其中存在遞歸，但這就是我無法理解此示例中的遞歸如何工作的問題。
3 回答
蕪湖不蕪
TA貢獻1796條經驗 獲得超7個贊
它定義了一個生成器- 一個稱為“ sieve”的流轉換器，
Sieve s = while( True ): p := s.head s := s.tail yield p -- produce this s := Filter (nomultsof p) s -- go nextprimes := 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)
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+1Filter 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)
實際上接受并實現了兩 對實現-一對用于此問題的試驗部門篩網，另一對用于通過計算直接減去每個素數的倍數（也就是真正的Eratosthenes篩子）的有序去除（兩者都是當然不推遲）。在Haskell，removemultsof
multsof p n = rem n p==0 remove m xs = filter (not . m) xs multsof p = [p*p, p*p+p..] remove m xs = diff xs m
（如果他只是推遲選擇實際的實現方式...）
至于推遲的代碼，在帶有“列表模式” 的偽代碼中，
primes = [2, ...sieve primes [3..]] sieve [p, ...ps] [...h, p*p, ...nos] = [...h, ...sieve ps (remove (multsof p) nos)]
添加回答
舉報
0/150
提交
取消