2

我对 SML 代码非常陌生，我正在尝试创建一个函数，该函数返回所有素数的列表，直到用户给出的数字。除了我的数字、索引和 lst 变量不断出现未绑定变量或构造函数错误外，我的大多数函数都在工作。代码应该使用两个辅助函数来遍历两个索引并将它们相乘，从而将非素数从列表中取出。这是我的代码：


fun removeMult (lst,n) = if null lst then lst else if hd lst mod n = 0 then removeMult(tl lst, n) else (hd lst) :: removeMult(tl lst, n);

fun helpertwo(lst, ind : int, n : int, indtwo : int) = if indtwo = n then lst else helpertwo(removeMult(lst , ind*indtwo),ind,n,indtwo+1);

fun test(lst,number,index) = 
if 
 number = index 
then 
 lst 
else
 helpertwo(lst, index, number, 2);
 test(lst,number,(index+1));

fun primes (n : int) = 
if 
 (n <= 1)
then
 []
else
  makelist(n);
  removeMult(lst , 1);
  test(lst, n , 2);
4

2 回答 2

2

重新缩进代码给出了这样的结果：

fun test(lst,number,index) = 
    if 
    number = index 
    then 
    lst 
    else
    helpertwo(lst, index, number, 2);
test(lst,number,(index+1));

fun primes (n : int) = 
    if 
    (n <= 1)
    then
    []
    else
    makelist(n);
removeMult(lst , 1);
test(lst, n , 2);

有些表达式根本不是函数的一部分，这就是为什么参数不在范围内的原因。实际上，您可以像这样有多个表达式else：

    else
    (helpertwo(lst, index, number, 2);
     test(lst,number,(index+1)))

但这在您的情况下不起作用，因为helpertwo没有副作用，所以真正的解决helpertwo方法是以某种方式使用结果。

于 2020-01-19T11:06:56.757 回答
1

这是使用筛子生成素数的另一种方法。

它不是特别有效，但它演示了惰性流。

流有点像一个列表，除了尾部用一个尚未计算的函数表示。下面的流的特定定义没有办法表示“流的结束”，严格的列表必须这样做。但由于素数是无限的，因此在概念上也可以存在包含它们的流。

datatype 'a stream = Cons of 'a * (unit -> 'a stream)

素数是自然数的子集，

fun nats i =
  Cons (i, fn () => nats (i+1))

fun take 0 _ = []
  | take 1 (Cons (x, _)) = [x]
  | take n (Cons (x, stream)) = x :: take (n-1) (stream ())

- take 10 (nats 0);
> val it = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] : int list

至于使用筛子挑选素数，请参阅Sieve of Eratosthenes (Wikipedia) 的动画：我们挑选第一个元素（从 2 开始）并删除后续的倍数（4、6、8、...）。我们选择下一个元素（为 3）并删除后续的倍数（6、9、12、...）。我们选择下一个元素（5，因为 4 已被划掉）并划掉后续的倍数（10、15、20，...），依此类推。

使用惰性流的递归解决方案可能看起来像

fun sieve (Cons (n, stream)) =
  Cons (n, fn () => sieve (remove_multiples n (stream ())))

and remove_multiples i =
  filter (fn n => n mod i <> 0)

and filter p (Cons (x, stream)) =
  if p x
  then Cons (x, fn () => filter p (stream ()))
  else filter p (stream ())

这是一个递归的、惰性的定义，因为它在延迟计算sieve的内部调用自身。fn () => ...它会逐步过滤掉更多的倍数，因为它不仅使用删除了一个元素的流调用自身，而且在每次递归调用时删除了多个元素的流。

您可以取前 10 个素数：

fun primes n =
  take n (sieve (nats 2))

- primes 10;
> val it = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] : int list

或者，您可以取谓词适用的第一个素数：

fun takeWhile p (Cons (x, stream)) =
  if p x then x :: takeWhile p (stream ()) else []

fun primesUpto n =
  takeWhile (fn p => p <= n) (sieve (nats 2))

- primesUpto 100;
> val it =
    [2, 3, 5, 7, 11,
     13, 17, 19, 23,
     29, 31, 37, 41,
     43, 47, 53, 59,
     61, 67, 71, 73,
     79, 83, 89, 97] : int list

如果您想要更高效但仍然实用且懒惰的策略，请查看轮筛。

于 2020-01-21T22:23:29.117 回答