SML：故障追蹤篩功能

Question

我有點困惑功能發現素數。我給出如下：

fun divides x y = (y mod x = 0); 

fun sieve [] = [] 
    | sieve(x::L) = x::sieve(filter (not o (divides x)) L); 

在sieve，我知道分x是divides部分應用程序。它只是返回一個函數，檢查傳遞給它的任何東西是否可以被x整除。

假設我打電話給sieve([2, 3, 4, ..., 10])。

然後在第一個遞歸調用，我會得到

2::sieve(filter(not o (divides 2)) [3, 4, 5, ..., 10]) 

2::sieve([3, 5, 7, 9]) 

2::3::sieve(filter(not o (divides 3)) [5, 7, 9]) 

2::3::sieve([5, 7]) 

2::3::5::sieve(filter(not o (divides 5)) [7]) 

2::3::5::7 

這是否正確？

感謝檢查，

bclayman

Answer 1

你的理解是正確的（雖然你的最後一行應改爲2::3::5::7::[]）。此代碼似乎是famous piece of Haskell code的SML修改。在Haskell版本中，primes被定義爲概念上無限的懶惰列表（最終，例如take 100 primes會爲您提供前100個素數）。上面給出的鏈接對基本邏輯有很好的解釋（不依賴於懶惰列表）。有多種方法可以在SML中實現惰性列表。爲了好玩，你可能想嘗試製作一個更接近Haskell版本的SML版本。