SML - 列表替换函数的迭代翻译

Question

我相信我在将第一个函数转换为仅使用赋值和循环方面处于正确的轨道上。我知道这违背了函数式编程，但这是教授想要的。

递归函数：

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 处发现语法错误

我希望能帮助调试，或者也许有一种更干净的方法来完成此迭代函数。

Answer 1

为什么哦为什么他不想要那个？没关系...

有很多问题。

1. 您在不需要的地方使用了许多分号。然而，这不是语法错误。
2. 您忘记了 if 语句中的序列 (exp1; exp2) 周围的括号。只允许排除 let..in..end 表达式的“in”部分中的括号。
3. 您将 temp 作为引用类型（使用 := 和 !）。然而，您还没有将其设为参考。这意味着您的输入变量 z 必须作为参考给出。如果这是您想要的，那么它与原始的子功能不匹配。
4. 原始子函数将自身限制为相等类型。但是，如果情况并非如此，那么您的 !temp <> null 将进行限制。使用 List.null 函数代替。
5. 当序列停止时，最后一个 !ret; 处的分号不应该出现，否则 end 将成为序列的一部分，从而失败。
6. 您忘记在条件的其他部分取消引用ret。
7. 您已切换 cons (::) 的参数。 Cons 的类型为 'a * 'a list，因此采用一个元素，然后采用一个元素列表。解决此问题并仍然保留元素顺序的一种方法是使用追加 (@) 函数，然后将要追加的元素放置在单例列表中。然而，有很多方法可以更好地处理这个问题，因为追加函数在大列表上的表现非常差。

以下是一个有效的函数：

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

这​​里可以改进的一个明显的事情是您始终使用相同的值更新 temp。所以这个可以排除掉。并且条件可以改为 case

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