0

文字列と文字列のリストのリストを取得し、渡された文字列を含むが渡された文字列を含まない各リスト内のすべての要素のリストを返すこの関数があります。

myfilter([["a","b"],["c","d"],["e","a","x"]], "a") -> ["b","e","x"]

fun myfilter(list : string list list, s : string) =
case list of
    [] =>  []
   |xs::xs' => case all_except_option(s, xs) of (* helper function that does it for a string and a list of strings *)
                   NONE => []
                  |SOME n => if n = xs
                             then myfilter(xs',s)
                             else n@myfilter(xs',s)

ご覧のとおり、これは再帰関数であり、末尾再帰関数に変換したいと考えています。末尾再帰の例には精通していますが、上記の関数でそれを行う方法がわかりません

4

1 に答える 1

6

末尾再帰を考えるとき、次に考えるのは「アキュムレータ」です。

関数が末尾再帰ではない理由は、何らかの結果を取得するために自分自身を呼び出し、その結果に対して何かを実行する必要があるためです。その計算を再帰呼び出しに移すことができれば、それは末尾再帰です。

この場合、あなたが行っている計算は、2 つのリストをまとめているということです。let ... in ... endしたがって、解決策は、3 番目のパラメーター (アキュムレータ) を取る内で宣言された関数になります。その後、アイテムをアキュムレータに追加できます。

良い例は、末尾再帰階乗関数です。通常の階乗関数は次のとおりです。

fun fact 0 = 1
  | fact x = x * fact (x-1)

末尾再帰にするために、アキュムレータを取るローカル関数を定義し、そこで乗算を行います。

fun fact x =
let
  fun fact' 0 acc = acc
    | fact' x acc = fact (x-1) (x*acc)
in
  fact' x 1
end

1 を掛けても効果がないため、アキュムレータの開始値として 1 を使用します。

それ以外にも、コードを改善するためにできることがいくつかあります。ここでこれを行う多くの人々に気づきました：

fun foo xs =
case xs of
    []      => ...
  | (x::xs) => ...

単に行う方がはるかに良い場合:

fun foo []      = ...
  | foo (x::xs) = ...
于 2013-01-31T09:38:10.410 に答える