Что является причиной того, что мои переменные SML не связаны? - PullRequest
Новая
       36

Что является причиной того, что мои переменные SML не связаны?

2 голосов
/ 19 января 2020

Я очень новичок в коде SML и пытаюсь создать функцию, которая возвращает список всех простых чисел вплоть до числа, заданного пользователем. У меня работает большинство функций, за исключением того, что я продолжаю получать несвязанную переменную или ошибку конструктора для моих переменных number, index и 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);

Ответы [ 2 ]

2 голосов
/ 19 января 2020

Повторное выделение кода дает что-то вроде этого: 

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 в некотором роде.

1 голос
/ 22 января 2020

Вот альтернативный способ генерации простых чисел с использованием сита.

Это не особенно эффективно, но демонстрирует ленивые потоки.

Поток похож на список, кроме Хвост представлен функцией, которая не была оценена. Конкретное определение потока ниже не имеет способа представить «конец потока», который обязательно должны иметь строгие списки. Но так как простые числа бесконечны, поток, который их содержит, также может быть концептуально. 

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

Что касается выбора простые числа с использованием сита, см. анимацию Сито Эратосфена (Википедия): Мы выбираем первый элемент (начиная с 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

Если вы хотите более эффективную, но все еще функциональную и ленивую стратегию, имейте посмотрите на колесное сито .

...