Let and Efficiency

（Let表达式和效率）Let and Efficiency

使用Let表达式以避免重复计算

思考下面的代码和其递归调用，别担心null、hd、tl，它们只是ML的内置函数。
参考：https://smlfamily.github.io/Basis/list.html#SIG:LIST.list:TY:SPEC

fun bad_max (xs : int list) =
  if null xs
  then 0 (* 糟糕的风格，后续修复*)
  else if null (tl xs)
  then hd xs
  else if hd xs > bad_max (tl xs)
  then hd xs
  else bad_max (tl xs)

let x = bad_max [50,49,…,1]
let y = bad_max [1,2,…,50]

快速vs不可用

我们注意到，第一行调用没有任何问题，运算速度很快。但是第二行调用缺似乎陷入了无尽的循环，很明显它是不可用的。

导致bad_max函数不可用的主要是下面的代码片段，因为它对自己进行了大量的重复调用。

if hd xs > bad_max (tl xs)
then hd xs
else bad_max (tl xs)

下图是分别对bad_max第一行调用和第二行调用的分析。可以看到，第二行调用会对bad_max调用将近次！大约会运行3.5年以上！

所以，关键是不要做重复的计算，将递归调用的结果保存到一个本地绑定是必要的。

改进

fun good_max (xs : int list) =
  if null xs
  then 0
  else if null (tl xs)
  then hd xs
  else
    let val tl_ans = good_max(tl xs)
  in
    if hd xs > tl_ans
    then hd xs
    else tl_ans
  end