F＃PurelyFunctionalDataStructures WeightBiasedLeftistHeap ex 3.4

Question

私は岡崎の純粋関数型データ構造に取り組んでおり、物事のF＃実装を構築しようとしています。また、本に記載されている演習も行っています（かなり難しいものもあります）。さて、元の2パスの実装ではなく、シングルパスで実行されるようにWeightBiasedLeftistHeapのマージ関数を変更する必要がある演習3.4に固執しています。

私はまだこれを行う方法を理解することができず、いくつかの提案を望んでいました。 SOに別の投稿がありました男がmakeT関数をほとんどインライン化することによってSMLでそれを行うところ。私はこのルートを使い始めました（コメントセクション3.4 First Tryで。しかし、これは実際にはシングルパスで実行されていないと思ったため、このアプローチを放棄しました（リーフに到達するまで続き、ツリーを巻き戻して再構築します）。それをまだ2パスマージであると解釈するのは間違っていますか？

こちらはWeightBiasedLeftistHeapの完全な実装へのリンク。

F＃でこれを実行しようとして失敗したのは次のとおりです： ジェネラコディセタグプレ

Answer 1

最初の質問は、「ワンパス」アルゴリズムを構成するものは何かということです。単一のトップダウンループとして自然に実装できるものが適格です。対照的に、再帰（単純にコンパイルされたもの）には通常2つのパスがあり、1つは下降途中、もう1つは上昇中です。 末尾再帰は簡単にループにコンパイルでき、通常は関数型言語です。 末尾再帰のモジュロ短所 も同様ですが、あまり一般的ではありません。 、最適化。ただし、コンパイラが末尾再帰のモジュロ短所をサポートしていない場合でも、そのような実装を手動でループに簡単に変換できます。

末尾再帰のモジュロ短所は、通常の末尾再帰と似ていますが、末尾呼び出しがコンストラクターでラップされている点が異なります。コンストラクターは、再帰呼び出しの前に割り当てて部分的に入力できます。この場合、戻り式をT (1+size(a)+size(b)+size(c),x,a,merge(b,c))のようなものにする必要があります。ここで必要な重要な洞察（他のSOスレッド）は、結果がどのくらい大きくなるか、したがって新しいツリーのどちら側に進むべきかを知るためにマージを実行する必要がないということです。これは、merge(b,c)のサイズが常にsize(b)+size(c)であり、マージの外部で計算できるためです。

通常の左翼ヒープの元のrank関数は、このプロパティを共有しないため、この方法で最適化できないことに注意してください。

次に、基本的に、makeTへの2つの呼び出しをインライン化し、また size(merge(b,c))形式の呼び出しをsize(b)+size(c)に変換します。

この変更を行うと、結果の関数は元の関数よりも大幅に遅延します。これは、再帰的マージを評価する前に 結果のルートを返すことができるためです。

同様に、ロックとミューテーションを含む並行環境では、新しい実装は、ツリー全体をロックするのではなく、途中で各ノードのロックを取得および解放することで、大幅に多くの同時実行をサポートできます。 （もちろん、これは非常に軽量のロックにのみ意味があります。）

Answer 2

質問を正しく理解したかどうかは正確にはわかりませんが、これが私の試みです-現在、merge操作は、mergeへの再帰呼び出し（これが最初のパスです）と、ヒープの終わりに達したとき（最初のパス）を実行しますmatchの2つのケース）、新しく構築されたヒープを呼び出し元に返し、makeTを数回呼び出します（これが2回目のパスです）。

mMakeTを単にインライン化することが、私たちに求められていることだとは思いません（はいの場合は、inlineをmakeTに追加するだけで、コードを読みにくくすることなく実行できます：-））。

ただし、実行できることは、merge関数を変更して、「残りの作業」が関数として再帰呼び出しに渡される継続渡しスタイルを使用することです（したがって、スタックに保留中の作業はありません）最初のパスが完了した後に実行されます）。これは次のように行うことができます： ジェネラコディセタグプレ

これが正しい答えであるとは完全には確信していません。パスは1回だけ実行されますが、（続きの）集約された作業は、パスが2倍長いことを意味します。ただし、これを簡単にする方法がわからないため、正しい答えかもしれません...