SML:故障跟踪Sieve函数

Question

我对一个寻找素数的函数感到有点困惑。我得到了以下信息：

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

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

在sieve中，我知道divides 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版本。