这是糟糕的代码,但它有效。我只是想知道这个递归调用如何分辨哪个数字最大/最大?试着解释一下,就好像我7岁一样:)
fun badmax (xs : int list)=
if null xs
then 0
else if null (tl xs)
then hd xs
else if hd xs > badmax(tl xs)
then hd xs
else badmax(tl xs)
先读取null
、tl
和hd
。一些提示可以帮助您入门。
fun badmax (xs : int list)=
if null xs <- If the list is empty, return 0
then 0
else if null (tl xs) <- If there is nothing returned by `null (tl xs)`,
we will return hd xs.
Q: Are you sure there is anything left in `hd xs`?
Note that if there is nothing left, calling
`hd xs` will raise exception. How can you be sure?
then hd xs
else if hd xs > badmax(tl xs) Q: What are we comparing here?
Think about what does `badmax(tl xs)`
return and why would we return `hd xs`
if the condition is satisfied.
Again, ask why `hd xs` and `tl xs` are legal.
then hd xs
else badmax(tl xs) Q: Why would we want to return `badmax(tl xs)`
空列表中最大的元素不是 0。
您可以使用异常处理空列表的特殊情况:
fun max [] = raise Empty
| max [x] = x
| max (x::xs) = case max xs of
y => if x > y then x else y
您可以通过一次替换一个表达式来运行它(如数学(:
max [3,9,7]
~> case max [9,7] of y1 => if 3 > y1 then 3 else y1
~> case (case max [7] of y2 => if 9 > y2 then 9 else y2) of
y1 => if 3 > y1 then 3 else y1
~> case (case 7 of y2 => if 9 > y2 then 9 else y2) of
y1 => if 3 > y1 then 3 else y1
~> case (if 9 > 7 then 9 else 7) of
y1 => if 3 > y1 then 3 else y1
~> case 9 of y1 => if 3 > y1 then 3 else y1
~> if 3 > 9 then 3 else 9
~> 9
由于情况不同,中间结果看起来很复杂。您可以使用let-in-end以类似的方式定义函数,但中间结果可能同样令人困惑。
fun max [] = raise Empty
| max [x] = x
| max (x::xs) = let val y = max xs
in if x > y then x else y
end
有一个名为Int.max
的库函数,它接受两个整数的元组并返回较大的整数。它使代码和中间结果看起来更整洁:
fun max [] = raise Empty
| max [x] = x
| max (x::xs) = Int.max (x, max xs)
您可以"手动"运行该函数以查看其工作原理:
max [3,9,7,5,6]
~> Int.max (3, max [9,7,5,6])
~> Int.max (3, Int.max (9, max [7,5,6]))
~> Int.max (3, Int.max (9, Int.max (7, max [5,6])))
~> Int.max (3, Int.max (9, Int.max (7, Int.max (5, max [6]))))
~> Int.max (3, Int.max (9, Int.max (7, Int.max (5, 6))))
~> Int.max (3, Int.max (9, Int.max (7, 6)))
~> Int.max (3, Int.max (9, 7))
~> Int.max (3, 9)
~> 9
不过,列表越长,调用堆栈就越长。
所以你可以写一个尾递归版本:
(* Keeps the current largest integer in an extra argument, y *)
fun maxhelp ([], y) = y
| maxhelp (x::xs, y) = maxhelp (xs, Int.max (x, y))
fun max [] = raise Empty
| max (x::xs) = maxhelp (xs, x)
当您手动运行相同的输入时:
max [3,9,7,5,6]
~> maxhelp ([9,7,5,6], 3)
~> maxhelp ([7,5,6], Int.max (9, 3))
~> maxhelp ([7,5,6], 9)
~> maxhelp ([5,6], Int.max (7, 9))
~> maxhelp ([5,6], 9)
~> maxhelp ([6], Int.max (5, 9))
~> maxhelp ([6], 9)
~> maxhelp ([], Int.max (6, 9))
~> maxhelp ([], 9)
~> 9
在第一个版本中,Int.max
被调用,一个数字作为一个操作数,一个递归调用作为另一个操作数,递归调用依赖于另一个递归调用,然后才能解析任何Int.max
。
在第二个版本中,Int.max
用两个数字调用,结果存储在参数中以maxhelp
。因此,当maxhelp
进行递归调用时,它取决于Int.max
被解析,而不是相反。这更整洁,因为Int.max
不是递归的。