F# でFree MonadとOperational Monad(未完成)

F#

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

JavaでFree Monadを実装する際のテクニックをxuweiさんが解説されているので、F#側も少し説明してみようと考えた次第です。

筆者はCLIやジェネリックに詳しくないので、そのあたりゆるく書きます。 変なこと書いてたらごめんなさい…。

なお、関連するつぶやきのまとめは以下にあります(xuweiさん、ありがとうございます)。

F# でFree MonadとOperational Monad - Togetterまとめ

現物

https://github.com/pocketberserker/free-monad-fsharp/tree/4466903b5fa09f4e4c67598248a56fa186b63bf7

この時点での話をします。

記事タイトルに未完成とついている理由は、Operational Monadが正しく動いているという自信を持てないためです(動かしてはみたが、自動テストまでもっていけていない)。

Free.resume

Java版の解説記事で、以下のように書かれています。

Scalazでの現行versionがAny型を使っているのと同じように、Gosubの型パラメータにはjava.lang.Object型を当てはめておけば、(C#やF#はどうなのか知らないが)Javaではtype erasureのお陰で、べつに普通に動きます。

しかし、java.lang.Objectを明示的に使うのは気持ち悪い*3わけです。

F#ではobjをあてはめるとInvalidCastExceptionが発生するため動きません。 クラスでは変位指定できずtype eraseもされないため、型があいません。 ちなみに型推論に任せるとobjと推論されます。

というわけで、基本はJava版と同様の方式をとっています。 Monadic Trampoline | F# Snippetsを参考にすればもっと良い実装になるかもしれませんが、最適化されるのかわかつていない*1ので試してません。

Coyoneda

Coyonedaは、GHCではRank2Types(他の環境はよく知らない)、Scalazでは抽象タイプを用いて実装されています。 しかし、F#にはこれらと同等の機能がありません。 そこで抽象メソッドと型パラメータでの解決を試みましたが、以下のコードはコンパイルできません。

[<Sealed>]
type CoYoneda<'F, 'A>(fi: 'F) =
  abstact member Func : 'I -> 'A

module CoYoneda =
  let apply fi k =
    { new CoYoneda<_, _> with(fi) with
      member this.Func(x) = k x }

型が解決できないためです。 仕方がないので、2つの案を考えました。

  • obj -> 'A で代用する
  • ダウンキャスト + applyするスコープでのみFuncを呼び出すよう心掛ける

現状は後者ですが、これはこれで面倒くさい(型を片っ端から明示しないといけない)ので良かったのか悪かったのか。 よさそうな案があれば教えていただきたく…。

https://github.com/pocketberserker/free-monad-fsharp/blob/4466903b5fa09f4e4c67598248a56fa186b63bf7/FSharp.Monad.Free/CoYoneda.fs#L14

確証がないので何とも言えませんが、今の実装で型推論にたよるとすぐにInvalidCastExceptionになる予感がします。

Operational

Freeモナドを超えた！？operationalモナドを使ってみよう - モナドとわたしとコモナド ScalaでOperational Monadできた - scalaとか・・・

上記記事を参考に実装してみましたが、型略称を定義するのが思ったよりもつらかったのでFreeのままです…。

https://github.com/pocketberserker/free-monad-fsharp/blob/4466903b5fa09f4e4c67598248a56fa186b63bf7/FSharp.Monad.Free/Operational.fs

今のinterpretは、resumeに指定する最初の型パラメータ2つを同じ型にすることでごまかしています。 このためunitを指定する機会が激減し(値をとりたいことのほうが多い)、Free型用のコンピュテーション式で使用可能だった do! がほぼ使い物にならなくなっています。 無意味な値を捨てたい場合はlet! _ = ...で代用して回避しています。 Scalazに存在するIO型(型パラメータがつかないやつ？)を真面目に実装すればなんとかなるかもしれませんが、IO Monadまで実装するのはつらそうだったので諦めました…。

感想

機能が限られた中でこういった型レベルプログラミングを行う場合、Type Erasure方式のほうが融通が利く気がしています。 もちろん型情報が残る場合の利点も多いので、一概にどうこう言えるものではありませんが…。

*1:64bitReleaseビルドは最適化されることは把握しているが…