技術memo

関数型ゴースト

シーケンスのソート後の順番を、元の順番を保ったまま取得したい

Twitterお題が出されたので、F# でやってみました。

sortして、indexとzipして、またsortし直すなんて、「ずいぶんとダサいコードを書いてるのね!」って思いました。*1

例のコードの「人」と「車」のデータ型にcarRankinghumanRankingとがあるのも、型の利用しやすさを考えるとちょっと微妙に思えるので、それとなく改修したり。単に「元のデータとランキング結果のタプル」として取得することにします。

解法

アルゴリズム的には、以下の形です。コードを見たほうが早いですけどね。

  1. 「元のシーケンスの要素と参照セルのペア」のリスト(配列)を作る
  2. 1.のリストをそのまま置いておいて、キーでソートしたシーケンスを生成
  3. 2.のシーケンスを列挙して、参照セルにソート後のインデックスを破壊的代入*2
  4. 1.のリストの参照セルにはソート結果のインデックスが入ってるので、参照セルを不変な値に変換

破壊的代入の辺りが微妙にダサい*3*4ので、その辺りうまくやれそうなサンプルがあるといいですね。どなたか。

考え方

設計・実装の流れは、概ね以下のイメージです。

  1. データ型を決める
    • Human, CarRanking属性は含めたくない
  2. 関数のシグネチャを決める
    • 個別のデータ型に依存したくない → 型変数にしてしまう
    • ランキングのソート条件を指定するには、キーを取得する関数を渡すか、またはIComparerを渡すか
    • 戻り値はシーケンスの要素と順位のタプルにする
  3. 関数を書いてみる。宣言部分だけでも*5
  4. テストを書く。とにかく書く。書いて動かしてみる。

問について

お題の問に関して、私なりに回答してみます。

  1. makeCarRankingをHumanにも使えるように汎用的にするにはどうしたらいいか?

→ Generic関数を使います。 この場合はkeySelectorを引数として渡すことで、個別のデータに関わる処理を外出ししました。 型クラスやクラス継承(インターフェース)で多相性を持たせるのも手段ではありますが、とりあえずのところ、こうしてしまうのが手っ取り早いのではないでしょうか。*6

  1. makeCarRankingのように全体を見てから全部の要素に値を設定する操作はどうしたらスマートか?

→ 機能を区切った関数の内部で、部分的に副作用を使ったコーディングをするのが楽そうです。 完全に純粋にやる方法もありそうですが、純粋さにこだわるよりは、むしろ関数外部に見せるシグネチャが扱いやすいものかどうか、よく考えたほうが良いと思います。

ということで今回はこの辺りで。

追記

*1:冗談です。

*2:論理的破綻!(冗談です)

*3:F#的には「関数全体で見れば参照透明」なので気にする必要もなさそうですが

*4:空間や時間的な最適化を考えるなら、Array.Sortを使うとか、もっとやりようはありそう

*5:テスト駆動開発っぽい

*6:F#には型クラスはありません。OCaml等ならFunctor(モジュールの機能であってアプリカティブやモナドとは違う話)が使えそうな気がします[要出典]