スキップリストとLINQ

スキップリストを.Net上で実装したライブリをLINQ対応にしたいのだが、中々上手く方針がまとまらない。

AggregateとかSum, Min, Maxとかはノードを引数にとるラムダ式ではなくノードと階層を引数にとるラムダ式を受け取るようにせざるを得ないのでLINQへのつじつまあわせはできない。これは、(ノード,階層)のペアが、区間 [ノード, ノード.Next[depth]) = [ノード, ノード.Next[depth].Prev[0]] に対応するためだ。本当はこれらをEnumerable.Aggregate等と同じように使えるようにしたいのが一番やりたい事だけどそれは無理そう。

でも、IEnumerableの実装(最下層を単純に列挙する)とかICollectionとかインタフェースの実装は最低限やっておくべきだろう。それから、First, Lastを現状のFind, FindLastで
置き換えて高速化はできるだろう。TakeWhileなんかもこれらができれば直ぐだ。

ただし、これらは全部、対応する区間が連続である事が前提なんだよな。そこらへん勝手に仮定して良いのだろうか。

例えばバイナリサーチのようなソートされた構造を前提にした操作とLINQの対応ってどうなっているのか等等、IEnumerableへの拡張メソッドでないコレクションクラス固有のLINQ実装が存在するのか調べておくと後の方針が立て易そうだ。

---

追記：
そういえば、AggregateメソッドがとるInitial引数は本当は必要ないなあ。初期値としてInitialをセットしてから逐次足しこんでいく実装になっているけれど、初期値を最初の一つにすればInitial引数は必要ない。Enumerable.Aggregate メソッドには三つのオーバーロード(一つ目, 二つ目)があって、今までのスキップリストライブラリのAggregateメソッドの定義はこの一つ目と二つ目の折衷みたいな形になっていたが、Initial引数を失くすことにすれば、一つ目のEnumerable.Aggregateメソッドと見た目が同じになって使う上での混乱もなくなるだろう。

Initial引数は半群における単位元(加法における零)が指定される事を想定しているけれど、正しい数学用語としては、半群は単位元を必ずしも含まず、含む場合はモノイドというらしい。もちろん、半群に一つ要素eを追加して、それと他の要素との群演算をex=xe=xと定める事はいつでもできるから、半群はいつでもモノイドに拡張できる。でもこの事はコードとして実現しようとすると簡単ではない。通常は加法における0とか、重み付き平均における重み0の要素とか、単位元として振舞う要素が初めから含まれているが、そうでないケースもあるだろう。MaxやMinをAggregateを用いて実装する時、InitialとしてDouble.MinやDouble.Maxを指定するのは、正しいけど汚い。真の実数ならばMinやMaxを群演算として半群と見なした場合には単位元は存在しない(-∞や+∞を実数全体の集合に追加してやる事が前述したモノイドへの拡張に対応する)。総和計算を行う可換半群に単位元を持っている事を求めるのは、止められるならば止めた方が良いようだ。

そのうち、Aggregateメソッドのロジックを変更して、Initial引数を取らないようにしよう。