Skip to content

Instantly share code, notes, and snippets.

@pocketberserker
Last active December 20, 2015 00:49
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save pocketberserker/6044257 to your computer and use it in GitHub Desktop.
Save pocketberserker/6044257 to your computer and use it in GitHub Desktop.

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

発表場所

.NET基礎勉強会

トゥギャッター

http://togetter.com/li/536460

資料のライセンス

CC-BY-SA 3.0

自己紹介

image

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

登壇経緯

image

イツモドオリダナー

さて

  • プログラミングをしているのであれば、一度と言わずデータ構造を実装しますよね?
  • ここでは、勉強がてらいくつも作ることにしたしましょう(こういう話もあるみたいですし 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# でも使いやすいようにするために

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

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

  • 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# で使ってみる

その2: FSharpx.Collections.Experimental.RoseTree

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

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

実装方針

  • レコードを使う

C# で使ってみる

その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 と行く方が少なくとも同じかより短い距離になる

実装方針

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

C# で使ってみる

まとめ

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

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

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

おまけ

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment