9

このような単純な追加関数（F＃）：

let rec app s t =
   match s with
      | [] -> t
      | (x::ss) -> x :: (app ss t)

関数は末尾再帰ではないため、sが大きくなるとクラッシュします。F＃の標準の追加関数は大きなリストではクラッシュしないため、別の方法で実装する必要があることに気付きました。だから私は疑問に思いました：appendの末尾再帰的定義はどのように見えますか？私はこのようなものを思いついた：

let rec comb s t =
   match s with
      | [] -> t
      | (x::ss) -> comb ss (x::t)
let app2 s t = comb (List.rev s) t

これは機能しますが、かなり奇妙に見えます。よりエレガントな定義はありますか？

4

3 に答える 3

26

従来型（末尾再帰ではない）

let rec append a b =
    match a, b with
    | [], ys -> ys
    | x::xs, ys -> x::append xs ys

アキュムレータ付き（末尾再帰）

let append2 a b =
    let rec loop acc = function
        | [] -> acc
        | x::xs -> loop (x::acc) xs
    loop b (List.rev a)

継続あり（末尾再帰）

let append3 a b =
    let rec append = function
        | cont, [], ys -> cont ys
        | cont, x::xs, ys -> append ((fun acc -> cont (x::acc)), xs, ys)
    append(id, a, b)

末尾以外の再帰関数を継続を使用して再帰に変換するのは非常に簡単ですが、私は個人的には読みやすさのためにアキュムレータを好みます。

于 2010-05-19T16:52:26.373 に答える
15

ジュリエットが投稿したものに加えて：

シーケンス式の使用
内部的に、シーケンス式は末尾再帰コードを生成するため、これは問題なく機能します。

let append xs ys = 
  [ yield! xs
    yield! ys ]

変更可能な.NETタイプの使用
Davidは、F＃リストは変更できると述べましたが、これはF＃コアライブラリのみに制限されています（機能の概念が壊れているため、ユーザーはこの機能を使用できません）。変更可能な.NETデータ型を使用して、変更ベースのバージョンを実装できます。

let append (xs:'a[]) (ys:'a[]) = 
  let ra = new ResizeArray<_>(xs)
  for y in ys do ra.Add(y)
  ra |> List.ofSeq

これは一部のシナリオでは役立つ場合がありますが、通常はF＃コードでの変更は避けます。

于 2010-05-19T17:44:52.987 に答える
1

F＃ソースを一目見ただけで、テールは内部的に変更可能であるように見えます。簡単な解決策は、要素を2番目のリストにまとめる前に、最初のリストを逆にすることです。これは、リストを逆にするとともに、末尾を再帰的に実装するのは簡単です。

于 2010-05-19T16:56:24.977 に答える