假設(shè)我們需要一個string * list * list 類型的值需要處理，并返回一個去掉制定字符串的string list 類型的程序。我們怎么處理？

這是一個非常簡單的程序，我像用這個非常簡單的問題介紹recursive 和 iterative 兩種方法。

首先定義比較字符串的函數(shù)，然后定義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) 

首先我們實現(xiàn)recursive 的函數(shù)

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中自動推導(dǎo)的類型是這樣的

可以看到他們是一模一樣的，只是后面一種不會棧溢出，開銷更小。

我為什么想寫這個內(nèi)容呢，我想說的是 一個語言根本不需要while這種循環(huán)類的關(guān)鍵字,遞歸更加的powerful。

那么問題來了，我的itreative是在編譯器尾遞歸優(yōu)化的情況下才做到不會導(dǎo)致棧溢出，如果編譯器十分的古老，沒有尾遞歸，這個時候你不需要循環(huán)么？

答案仍然是不需要，這是一個非常有趣的問題,我們可以通過continuation-passing style (CPS)來解決這件事，過一段時間，我會來填這個cps的坑。