dotnetbase.rst

F# ではじめるデータ構造の実装入門 木構造編

発表場所:	.NET基礎勉強会
トゥギャッター:	http://togetter.com/li/536460
資料のライセンス:	CC-BY-SA 3.0

自己紹介

• なかやん・ゆーき / ぺんぎん
• @pocketberserker / id:pocketberserker
• どこにでもいるふつーの新卒エンジニア（おーさか）
• F# / Scala / Erlang / Haskell
• 仕事は C++ と Unity3d(C#)…
• 「ククク… pocketberserker は Microsoft MVP for F# 四天王（※現状四人しかいない）の中でも最○」
• 過去に翻訳した記事: C# と F# の Async: C# の非同期の落とし穴

登壇経緯

イツモドオリダナー

さて

• プログラミングをしているのであれば、一度と言わずデータ構造を実装しますよね？
• ここでは、勉強がてらいくつも作ることにしたしましょう（こういう話もあるみたいですし https://twitter.com/mzp/status/222481402451595264 ）
• 環境基盤が同じ言語が複数あるとしたら、一度の実装で両方の言語で使いたいですね？
• C# と F# のどちらで書くか、と聞かれたら 私は迷いなく F# と答えます
• というわけで F# で書いて C# でも使えるように作る練習をしましょう

本日の対象データ構造

データ構造と言っても色々とあるので、木構造の中から以下のものをピックアップしてみていきます。

1. Microsoft.FSharp.Collections.Map （シグニチャ 、実装 ）
2. FSharpx.DataStructures.RoseTree -> FSharpx.Collections.Experimental.RoseTree
3. FSharpx.DataStructures.BKTree -> FSharpx.Collections.Experimental.BKTree

F# で実装したものを C# でも使いやすいようにするために

まずは以下の記事を読みましょう。

• C# から使いやすい F# コードの書き方 - ぐるぐる～

データ構造実装時によく使うものは以下

• CompiledName （C# 側での名前をいい感じに）
• CompilationRepresentation （名前衝突を避ける）
• Extension （拡張メソッドだよーと宣言）

あと、C# から使いやすいように IEnumerable を実装しておくと良いかも。

その1: Microsoft.FSharp.Collections.Map

https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/map.fsi

https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/map.fs

• FSharp.Core に存在する Map
• Immutable map
• Keyの比較によって順序付けを行う
• 内部実装は木構造
• thread-safe

実装方針

• 判別共用体は公開しない
• 判別共用体で型、アルゴリズムを実装 -> クラスでラッピング -> 公開用モジュールを作成

C# で使ってみる

// 発表者を突っ込む
var map = MapModule.Empty<int, string>()
    .Add(2, "bleis")
    .Add(6, "smallgeek")
    .Add(1, "kyon_mm")
    .Add(7, "pocketberserker");

Console.WriteLine("==== 一覧 ====");
foreach (var i in map)
{
    Console.WriteLine("{0} {1}", i.Key, i.Value);
}

Console.WriteLine("==== 偶数のみ ====");
foreach (var i in map.Where(e => e.Key % 2 == 0))
{
    Console.WriteLine("{0} {1}", i.Key, i.Value);
}

その2: FSharpx.Collections.Experimental.RoseTree

https://github.com/fsharp/fsharpx/blob/master/src/FSharpx.Collections.Experimental/RoseTree.fs

• Multi-way Tree
• 分岐が2のときは2分木（バイナリーツリー）
• 詳しくは この本 を読みましょう

実装方針

• レコードを使う

C# で使ってみる

var rose = new RoseTree<int>(1, LazyListModule.ofArray(new[] {
    new RoseTree<int>(2, LazyListModule.empty<RoseTree<int>>()),
    }));

その3: FSharpx.Collections.Experimental.BKTree

https://github.com/fsharp/fsharpx/blob/master/src/FSharpx.Collections.Experimental/BKTree.fs

• 距離空間を用いてデータの保持順序を決める
• root要素との距離が近いほど検索しやすい
• 既に距離が同じ要素が登録されている場合は、実装に使われている内部のデータ構造に依存

距離空間

あるクラスにインスタンスどうしの距離が定められたもので、以下のをルールを持つ

• 距離は常に非負
• 自分自身との距離は0
• a→b→c と行くより a→c と行く方が少なくとも同じかより短い距離になる

{- Haskellだよー -}
class Eq a => Metric a where
  distance :: a -> a -> Int

実装方針

• privateな関数では常に distance 関数を渡すようにする
• distance 関数を引数にとる Generic なラッパークラスを用意する

C# で使ってみる

var tree = BKTree.empty<int>();
tree = BKTree.Int.add(10, tree);

Console.WriteLine("==== データひとつ追加 ====");
foreach (var i in tree)
{
    Console.WriteLine(i);
}

tree = BKTree.Int.add(111, tree);
tree = BKTree.Int.add(1, tree);
tree = BKTree.Int.add(50, tree);

Console.WriteLine("==== さらにいくつか追加 ====");
foreach (var i in tree)
{
    Console.WriteLine(i);
}

Console.WriteLine("==== Linqる ====");
foreach (var i in tree.Select(n => n + 3000))
{
    Console.WriteLine(i);
}

まとめ

C# でも使える木構造を F# で実装するなら

1. 内部実装と公開クラスの実装を分ける
2. レコードを使ったりする
3. ラッパークラスを経由する

などを行えば、良い感じになると思います。

おまけ

• FingerTree を実装しようと半年ほど戦っていますが、多相の壁に阻まれている(?)ため今回の発表から除外することに…orz
• https://twitter.com/kinaba/status/7062808769