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版本。