SML - Итеративный перевод функции замены списка - PullRequest
Новая
       5

SML - Итеративный перевод функции замены списка

2 голосов
/ 07 марта 2011

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

Рекурсивная функция: 

fun sub (x, y, []) = []
  | sub (x, y, z::zz) = if x = z then y::sub(x, y, zz)
            else z::sub(x, y, zz);

Итерационный перевод: 

fun sub2 (x, y, z) =
    let val ret = ref []; val temp = z;
    in
        while !temp <> []
        do (if x = hd(!temp) then ret := !ret::y; temp := tl(!temp)
            else ret := ret::hd(!temp); temp := tl(!temp));
        !ret;
    end;

Я получаю следующие ошибкиработает на smlnj.Первый в строке с do, а второй в конце.

Ошибка: синтаксическая ошибка: замена END на EQUALOP

Ошибка: синтаксическая ошибка найдена в EOF

Буду признателен за помощь в отладке или, возможно, более понятный способ выполнения этой итеративной функции.

1 Ответ

4 голосов
/ 07 марта 2011

Почему он вообще этого не хотел?Не берите в голову ...

Есть довольно много проблем.

  1. Вы используете много точек с запятой, где они не нужны.Это, однако, не является синтаксической ошибкой.
  2. Вы забыли скобки вокруг своей последовательности (exp1; exp2) в своем операторе if.Разрешается исключать только круглые скобки в части «in» выражения let..in..end.
  3. Вы ссылаетесь на temp как тип ref (используя: = и!).Вы однако не сделали это реф.Это означает, что ваша входная переменная z должна быть указана в качестве ссылки.Если это то, что вы намереваетесь, то она не соответствует исходной подфункции.
  4. Исходная подфункция ограничивается типами равенства.Однако, если это не так, тогда ваш !temp <> null сделает ограничение.Вместо этого было бы "лучше" использовать функцию List.null .
  5. Точка с запятой в конце !ret; не должна быть там, когда ваша последовательность останавливается, иначе end будетстаньте частью последовательности, которая потерпит неудачу.
  6. Вы забыли разыменовать ret в другой части условия.
  7. Вы переключили аргументы cons (: :).Тип Cons имеет тип 'a * 'a list и, следовательно, принимает элемент, а затем список элементов.Один из способов исправить это и при этом сохранить порядок элементов - использовать функцию append (@) и затем поместить элемент для добавления в одноэлементный список.Однако существует множество способов сделать это лучше, так как функция добавления очень плохо работает с большими списками.

Ниже приводится функция, которая работает: 

fun sub2 (x, y, z) =
let 
  val ret = ref []
  val temp = ref z
in
  while not (null (!temp)) do 
    if x = hd(!temp) then 
      (ret := !ret @ [y]; 
       temp := tl(!temp))
    else 
      (ret := !ret @ [hd(!temp)]; 
       temp := tl (!temp));
  !ret
end

Oneочевидная вещь, которую можно улучшить, это то, что вы всегда обновляете temp одним и тем же значением.Так что это может быть учтено.И условие может быть изменено на случай вместо 

fun sub2 (x, y, z) =
    let 
      val ret = ref []
      val temp = ref z
    in
      while not (null (!temp)) do       
        (case x = hd(!temp) of
          true => ret := y :: !ret
        | false => ret := hd(!temp) :: !ret
       ;temp := tl (!temp));         
      rev (!ret)
    end

Особенно обратите внимание, как элементы добавляются не к результирующему списку, а к его переднему краю, а затем в конце получаемый список переворачивается дляправильный порядок.Это даст вам гораздо лучшую производительность в больших списках.Однако есть и лучшие способы сделать это, когда вы используете императивный стиль в SML.

Как вы уже видели, это можно сделать функциональным способом.Но это также можно сделать проще.Рассмотрим следующее, используя карту. 

fun sub3 (x, y, zs) = map (fn z => if z = x then y else z) zs
...