F# で高階型のエミュレーション

この記事では、F# で 高階型 (higher kinded types) をエミュレーションすることについて記述します。

本当は 函数型なんたらの集い 2014 in Tokyo - connpass で話そうと思っていたのですが、運営を考えると発表できる気がしなくなった*1ので、記事にしてお茶を濁します。

注意事項

• F# で推奨される実装、ガイドラインから逸脱した実装になっています
• 型安全かどうかは考察しません(時間が足りない)
• この記事をみただけで"F# は残念な言語"という判断を下すのは誤りです
• 専門家ではないので、厳密なことは書けません。生暖かい目で見守ってください。
• Haskell, Scala(z), Java のコードも登場します

参考文献?

• highj - Haskell-style type classes in Java - Google Project Hosting
• ocamllabs/higher · GitHub
• xuwei-k/free-monad-java · GitHub

本記事に登場する FSharp 実装まとめ

本記事で実装した型に幾つか修正、追加を行ったライブラリが下記になります。

pocketberserker/FSharp.Karma · GitHub

問題点: この世界に奴はいない

世の中には高階型というものが存在します。高階型については、

(もりそば)Scalaによる高階型変数 - Higher-kind Generics - ( ꒪⌓꒪) ゆるよろ日記

とかを読んでみてください。

高階型が存在しないとどういう問題点があるのかという話については、

関数を扱えるだけでは、モナドを表現するには不十分過ぎる - scalaとか・・・

を読みましょう。

さて、 F# も高階型をサポートしていない言語の一つです。

抽象化や共通化のみを考える場合、F# には overload や"静的に解決された型パラメータ"を使えば、解決できる部分もあります。 これらの機能を使って実装されたライブラリとしては

gmpl/FsControl · GitHub

があります。

しかし、型コンストラクタで高階型が要求されるような型クラスは、高階型がなければ実装が困難です。*2

解決案: ないなら…作るしかねぇ!

参考文献にあげた highj や higher、 free-monad-java では 高階型をエミュレーションするための型を用意しています。 この方法は、F# でも利用可能です。 本記事では free-monad-java のスタイルを採用して記述していきます。

// Scala の F[A] を表す型
type _1<'F, 'A> = interface end

_1 は 型パラメータを一つ持つ高階型です。 'F は対象の型を、 'A はその型がもつ型パラメータを表します。

今回は highj における μ の代替として判別共用体を用います。

例: Identity

最も簡単な(そして標準に存在しない型の)例として、Identity型を定義してみましょう。

// 同名の判別共用体を用意
// highj の Id.μ 、 free-monad-java の Id.z 相当
type Id = Id

// 実際の Id 型
type Id<'A> = { Value: 'A }
  with
    interface _1<Id, 'A>

まず、Id 型を表す高階型用の判別共用体 Id を用意します。

次に、実際に利用する Id 型に _1 を実装します。 こうすることで、その型が高階型であることを表現出来ます。

あとは、例えば Functor などを用意してあげれば、

type Functor<'F> =
  abstract member Map: ('A -> 'B) * _1<'F, 'A> -> _1<'F, 'B>

module Functor =

  // 任意の Functor を対象にできる
  let map (fa: Functor<_>) f a = fa.Map(f, a)

ダウンキャストによって、それなりに抽象化できます。

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Id =
  // functor は F# の予約語なので使用できない
  let functor_ = { new Functor<Id> with
    // fa は _1<Id, 'A> なので、Id<'A> ダウンキャスト可能
    member this.Map(f, fa) = (fa :?> Id<_>) |> map f :> _1<Id, _> }

例: Free

ここまでは、F# だと overload と 静的に解決された型パラメータを用いればよい話でした。

しかし、 Free Monad の実装には高階型が必要になるので、型パラメータでなんとかなるとは限りません。 Free Monad については検索したら色々と記事があるので探してください。

Haskell 実装

まずは、Free Monad の Haskell 実装から見てみましょう。 今回は ekmett 氏の free を参考にします。

https://github.com/ekmett/free/blob/a2008da7fe75b4cc80904d9bd3275e5772a28c91/src/Control/Monad/Free.hs#L103

f が高階型になっており、 Free 型コンストラクタ内で Free 型を持っています。

Scala 実装

Scala では Scalaz のものが有名です。

https://github.com/scalaz/scalaz/blob/2f80af1f512d80a2a531c1859f58b09f4002da1d/core/src/main/scala/scalaz/Free.scala#L50

S が高階型となっています。 Haskell での Free 型コンストラクタに対応する Suspend 型コンストラクタをみると

https://github.com/scalaz/scalaz/blob/2f80af1f512d80a2a531c1859f58b09f4002da1d/core/src/main/scala/scalaz/Free.scala#L17

Free を持つことがわかります。

_1 を用いてエミュレーション

Suspend を _1 を使って表現すると、次のようになります。

type private Suspend<'F, 'A> (a: _1<'F, Free<'F, 'A>>) = ...

あとはうまい具合に型を合わせてあげれば、Free Monadの完成です。 これに関しては本記事の内容ではないので、もっと詳しく知りたい方は

JavaでFreeモナドを表現するためのテクニックやexistential type(存在型)の話 - scalaとか・・・

を読んでください。 Java と F# での違いは

• F# は末尾再帰最適化される
• F# は type erasure ではないため、型パラメータの型が異なっていると InvalidCastException
• F# にてきとーに型推論させると、Gosubの型パラメータが obj に推論されて死ぬ(ので、結局明示しないとだめ)

あたりです。

問題点

• mixin がないので、既存の型に 1 を実装できない(Wrapper 型に対して 1 を実装するはめに)
• 明示的にキャストする必要があるので、ダウンキャストやアップキャストの嵐に

次回予告

もみあげ「やった、Free Monadができた...ん?」

GitHub「xuwei-k pushed to develop at xuwei-k/free-monad-java operational monad」

もみあげ「ナンデ!?ワイルドカードナンデ!?」

*1:想定以上に大規模になった...

*2:試していないので絶対にできないとは言えない。もしかしたら Map を持つ型などの制約をつければ実装できるかも…?