13

私は最近、多くの OCaml 標準ライブラリ関数を末尾再帰に書き直しています。これが単純な CPS 変換を必要としたことを考えると、なぜデフォルト バージョンがこのように書かれていないのか、私は困惑しています。

例として、標準ライブラリでは、 map は次のように定義されています。

let rec map f = function
    []   -> []
  | a::l -> let r = f a in r :: map f l

私はそれを次のように書き直しました：

let map f l =
  let rec aux l k = match l with
      []   -> k []
    | a::l -> aux l (fun rest -> k (f a :: rest))
  in aux l (fun x -> x)
4

2 に答える 2

9

私の経験では、重要な関数の末尾再帰バージョンは、多くの場合、スペース効率と時間効率をトレードオフします。言い換えれば、標準ライブラリの関数は、小さな入力に対して簡単に高速になる可能性があります。

于 2012-08-17T20:25:17.723 に答える
9

kさて、あなたのコードは、呼び出しスタック上のフレームのスタックではなく、ヒープ内のクロージャーの「リンクされたリスト」を構築して渡しています (各クロージャーは、前のクロージャーを としてキャプチャします)。

末尾再帰的に行うより一般的で同等の方法は、これまでの結果リストを渡し (効率的に前に追加することしかできないため、逆に)、最後にそれを逆にすることです。

let map f l =
  let rec aux l acc = match l with
      []   -> List.rev acc
    | a::l -> aux l (f a :: l)
  in aux l

（これは基本的に と同じですList.rev (List.rev_map f l)）

この場合、蓄積されるのは、クロージャーではなく、これまでの結果のリスト (逆) です。しかし、効果はまったく同じです。

どちらの場合も、ある種の中間表現 (入力リストと出力リスト以外) のために線形空間が必要なので、メモリ使用の複雑さに関しては、非末尾再帰バージョンよりも利点はありません。ヒープにはスタックよりも多くのメモリがあることは事実ですが、末尾再帰バージョンを使用すると、非末尾再帰バージョンよりも大きなリストで機能する可能性があります。絶対的なメモリ使用量に関しては、リスト オプションを累積するのがおそらく最も効率的です。これは、クロージャとスタック フレームの両方にオーバーヘッドがあるためです。

于 2012-08-17T23:18:07.507 に答える