假设我们需要一个string * list * list 类型的值需要处理，并返回一个去掉制定字符串的string list 类型的程序。我们怎么处理？
这是一个非常简单的程序，我像用这个非常简单的问题介绍recursive 和 iterative 两种方法。
首先定义比较字符串的函数，然后定义option的类型，为recursive和iterative
fun same_string(s1 : string, s2 : string) =
s1 = s2
fun all_except_option(lst, str) =
case lst of
[] => NONE
| ls::ls' => if same_string(ls,str)
then SOME ls'
else case all_except_option(ls', str) of
NONE => NONE
| SOME xs => SOME(ls::xs)
首先我们实现recursive 的函数
fun get_substitutions1(str_lst_lst, str) =
case str_lst_lst of
[] => []
| ls::lst => case all_except_option(ls, str) of
NONE => get_substitutions1(lst, str)
| SOME xs => xs @ get_substitutions1(lst,str)
再看看 iterative
fun get_substitutions2(str_lst_lst, str) =
let fun aux(lst, acc) =
case lst of
[] => acc
| ls::ls' => case all_except_option(ls, str) of
NONE => aux(ls', acc)
| SOME xs => aux(ls', acc @ xs)
in
aux(str_lst_lst, [])
end
可以看到，我们最上面的递归形式被我在夏目按改成了尾递归形式，尾递归形式的开销更小。
他们在repl中自动推导的类型是这样的
可以看到他们是一模一样的，只是后面一种不会栈溢出，开销更小。
我为什么想写这个内容呢，我想说的是 一个语言根本不需要while这种循环类的关键字,递归更加的powerful。
那么问题来了，我的itreative是在编译器尾递归优化的情况下才做到不会导致栈溢出，如果编译器十分的古老，没有尾递归，这个时候你不需要循环么？
答案仍然是不需要，这是一个非常有趣的问题,我们可以通过continuation-passing style (CPS)来解决这件事，过一段时间，我会来填这个cps的坑。
