在SML中获取列表的最大值

Question

在SML中获取列表的最大值

3

我目前正在学习SML，但是我很难理解下面的代码

fun good_max (xs : int list) =
  if null xs
  then 0
  else if null (tl xs)
  then hd xs
  else
    (* for style, could also use a let-binding for (hd xs) *)
    let val tl_ans = good_max(tl xs)
    in
      if hd xs > tl_ans
      then hd xs
      else tl_ans
    end

hd xs 是 int 类型，而 tl_ans 我认为是 list 类型。为什么这段代码能够工作？系统是如何评估递归的？如果您能使用xs = [3, 4, 5] 来展示这个过程，那将会很好。

- fardown

` let val y = old_max(tl[3,4,5]) in max(hd[3,4,5], y) end let val y = (let val y' = old_max(tl(tl[3,4,5))) in max(hd(tl[3,4,5],y')) end) in max(hd[3,4,5],y)

 let val y = (let val y' = old_max([5]) in max(4,y') end) in max(3,y)
        end
 let val y = 5 in max (3,y)
 5`

- fardown

好的。我在尝试将代码放入评论框时搞砸了。谢谢Andreas！我能够理解你的代码并将它应用到我的代码中。使用辅助函数使代码更优雅 :) 我犯的假设错误是因为在评估函数之前我没有替换所有分支。递归真的是一个具有挑战性的主题。 - fardown

顺便说一句，max函数已经作为Int.max存在于标准库中。此外，第三个case的右侧显然可以简化为max(x, goodMax xs) -- 我之所以没有这样做是为了展示let内部的规约方式。最后，我建议在空案例中抛出异常，因为0作为结果并不完全正确。总的来说，你可以将该函数简单地表达为一个fold，如下所示：fun goodMax [] = raise Empty | goodMax(x::xs) = List.foldl Int.max x xs。 - Andreas Rossberg

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andreas Rossberg · Accepted Answer

首先让我把这段代码重写为一个等价但更易读的版本：

fun max(x,y) = if x > y then x else y

fun goodMax(nil) = 0
  | goodMax(x::nil) = x
  | goodMax(x::xs) = let val y = goodMax(xs) in max(x,y) end

现在我们可以考虑如何评估goodMax([3,4,5])：从概念上讲，它将通过反复替换函数定义的相应分支来简化答案。

  goodMax([3,4,5])
= goodMax(3::[4,5])
= let val y = goodMax([4,5]) in max(3, y) end
= let val y = goodMax(4::[5]) in max(3, y) end
= let val y = (let val y' = goodMax([5]) in max(4, y') end) in max(3, y) end
= let val y = (let val y' = goodMax(5::nil) in max(4, y') end) in max(3, y) end
= let val y = (let val y' = 5 in max(4, y') end) in max(3, y) end
= let val y = max(4, 5) in max(3, y) end
= let val y = (if 4 > 5 then 4 else 5) in max(3, y) end
= let val y = 5 in max(3, y) end
= max(3, 5)
= if 3 > 5 then 3 else 5
= 5

我已将内部调用中的y改名为y'，以使其更清晰易懂。