再帰関数のスタックオーバーフローを倒す話 その1

再帰関数のスタックオーバーフローを倒す話を何回かに分けてします。

連載目次

• 再帰関数のスタックオーバーフローを倒す話 その1 ← 今回
  • CPSとCPS変換の話
• 再帰関数のスタックオーバーフローを倒す話 その1.5
  • F#での「末尾」についての話
• 再帰関数のスタックオーバーフローを倒す話 その2
  • .NETにおける末尾最適化の方法についての話
• 再帰関数のスタックオーバーフローを倒す話 その2.5
  • 継続モナドと、F#の残念さの話
• 再帰関数のスタックオーバーフローを倒す話 その3
  • すべてをあきらめて再帰をwhileに書き直す方法の話

はじめに

継続渡しスタイルもしくは継続渡し形式(Continuation Passing Style、以降CPS)という言葉を聞いたことがあるでしょうか。 今日はCPSの話をします。 前提知識は、F#のみです。

継続とは

CPSの前に、まずは継続の話です。 継続と言っても、継続的インテグレーションとか継続的デリバリとはまったく、これっぽっちも関係ありませんのでそういう話題を期待した人は回れ右。 これらの文脈では継続は「繰り返し」とかそんな風な意味を含んでいますが、今回扱う継続は「続き」とかそんな意味ととらえてください。

続きったって何の続きだ、となるわけですが、ざっくり説明すると、

「プログラムのある瞬間を考えたときに、その瞬間より後に実行される処理」

が継続です。

プログラムのデバッグでブレークポイントを貼って処理をブレークしたときに、「そのあとに実行される処理」ってあるじゃないですか。 あれをプログラミングの対象にしてしまおう、というような話だと思ってください。

let x = f 42 (* ここでブレークして、fから戻ってきた状態(fは実行済み) *)
printfn "%d" x

コメントに書いたような状態だと思ってください。 このときに、継続は

+---------+
| let x = | f 42
|         +------+
| printfn "%d" x |
+----------------+

この枠で囲われた部分です。 =の左側が計算されてからその結果が右側の変数xに設定されるので、let x =の部分も継続に含めています。

さて、これをプログラミングの対象にするにはどうすればいいでしょう？

継続を無名関数で表す

一つの方法として、プログラムを変形して継続を無名関数で表す、というのがあります。 やってみましょう。

f 42 |> (fun x ->
printfn "%d" x)

上のコードとこのコードが同じ動作をすることは分かるでしょうか。

先ほどはletの一部分が継続に含まれていたので、プログラミングの対象に出来なさそうでした。 それに対して、このコードでは先ほどの例と同じ継続は

          +-----------+
  f 42 |> | (fun x -> |
+---------+           |
| printfn "%d" x)     |
+---------------------+

この枠で囲われた部分です(|>演算子は使わないこともできるので含めていません)。 これなら、この関数自体をプログラミングの対象に出来ますね！

(* もはや値としての関数でしかない *)
let cont = (fun x -> printfn "%d" x)

これだけだとありがたみがさっぱりですが、継続は関数として表せる、ということがわかりました。

無名関数でletを代用する

先ほどの変形によって、letが消えたのに気づいたでしょうか？ letによって導入していた変数は、継続を表す無名関数の引数に変わりました。 letを無名関数で表すことは後で重要になってくるので、もう少し詳しく見てみましょう。

このようなプログラムがあったとします。

let x = f 42
let y = g x
let z = h y
printfn "%A" (x, y, z)

これをletを使わずに無名関数だけで書いてみます。

f 42 |> (fun x ->
g x |> (fun y ->
h y |> (fun z ->
printfn "%A" (x, y, z) )))

f 42より後ろを表す継続はf 42の戻り値をxとして引数で受け取ります。 そして、g xより後ろを表す継続はg xの戻り値をyとして引数で受け取ります。 h yより以下略。

このように、継続を起動した(継続を表す関数を呼び出した)側の結果は、引数として受け取り、その継続の中で使えます。

継続渡しスタイル(CPS)

fとgとhがそれぞれこのような関数だったとしましょう。

let f x = x / 2    // int -> int (intを受け取ってintを返す関数)
let g x = x + 10   // 同上
let h x = string x // int -> string (intを受け取ってstringを返す関数)

これを元にして、各関数が「自身の処理をした後の継続cont*1」を受け取れるようにしてみます。

let fCont x cont = x / 2 |> cont    // int -> (int -> 'a) -> 'a (intと「intを受け取って何か('a)を返す関数」を受け取って何か('a)を返す関数)
                                    // 元の関数での戻り値は、第二引数で渡される関数の引数になっている
let gCont x cont = x + 10 |> cont   // 同上
let hCont x cont = string x |> cont // int -> (string -> 'a) -> 'a (intと「stringを受け取って何か('a)を返す関数」を受け取って何か('a)を返す関数)
                                    // 元の関数での戻り値は、第二引数で渡される関数の引数になっている

このように、「自身の処理をした後の継続」を受け取る関数のことを、「継続渡しスタイルの関数」と言います。

元の関数では結果はそのまま呼び出し元に返していましたが、このバージョンではcontに結果を渡しています。 contは「自身を処理した後の継続」ですから、それに結果を渡すことによって、contの中で結果が使えるようにするためです。

fContはどうやって使えばいいでしょうか？ fであれば、例えばこのように使っていました。

let res = f 10
...

fContはこのように使います。

fCont 10 (fun res ->
...)

「無名関数でletを代用する」で見たような書き方になっていますね。 「無名関数でletを代用する」では、|>演算子を使って順番を入れ替えていましたが、継続渡しスタイルの関数を使う場合は不要です。

このように、継続渡しスタイルの関数を使って継続を渡すプログラミングスタイルが、「継続渡しスタイル(CPS)」です。

fCont 42 (fun x ->
gCont x (fun y ->
hCont y (fun z ->
printfn "%A" (x, y, z) )))

ここからは継続が関数として表せると何が嬉しいかを説明するための準備となることを説明します。

末尾呼び出し

末尾呼び出しというのは、関数を呼び出した後に結果を戻す以外にすることがないような関数呼び出しのことを言います*2。 さて、ではf1, f2, f3の中で末尾呼び出しされている関数はどれでしょうか？

let example x =
  if f1 x then f2 x
          else 10 + f3 x

答えは、f2だけです。

f1が末尾呼び出しじゃないというのは、f1を呼び出した後にthen節かelse節を実行する必要があることから分かります。

f2の後にelseがあるように思えるかもしれませんが、then節とelse節は二者択一であり、then節が選ばれたときにはelse節は実行されません。 then節ではf2を呼び出した後は何もすることなくその結果を戻すだけなので、f2は末尾呼び出しです。

f3の呼び出しは、その結果を使って10と加算するという処理がf3から戻ってきたときに必要です。 そのため、f3は末尾呼び出しではありません。

何が「末尾」になるのかは今回は横道なので深入りはしませんが、別の機会に(F#については)まとめようと思います。

末尾呼び出しの最適化

末尾呼び出しは「関数から戻ってきた後に結果を戻す以外にすることがないような関数呼び出し」でした。 何もすることがないのなら、関数呼び出しじゃなくて、単なるジャンプ命令に置き換えてしまえばスタックを消費しなくなっていいよね！ というのが末尾呼び出しの最適化です*3。

これが嬉しいのは、例えば再帰関数が末尾呼び出しになっている場合です*4。 このような再帰を末尾再帰と言ったりします。 末尾呼び出しが最適化されないと、再帰の回数が積み重なるとスタックオーバーフローを起こしてしまいます。 末尾呼び出しが最適化されることで、再帰の回数が積み重なってもスタックオーバーフローが起こらなくなるため、再帰の回数が多くなり得る関数は末尾呼び出しの最適化がかかるように末尾再帰の形に変形することがあります。 式木の変形など、単純に書くと末尾再帰にならない再帰は山のようにあるので、末尾再帰の形に変形する方法は重要です。

あ、一応言っておくと、末尾呼び出しの最適化がかかるかどうかは言語や処理系によって違いますので、 末尾再帰に変形したからと言ってスタックオーバーフローが起きなくなることが保証されるわけではありません。 自分の好きなあの言語、あの処理系、末尾呼び出しの最適化がかかるかどうか調べておくといいでしょう。

CPS変換による末尾再帰関数への変換

さて、話を継続に戻します。 CPSに変形(CPS変換)することで、自動的に末尾再帰の関数が手に入るのです！ なぜそうなるのかを見てみましょう。

継続渡しスタイルの関数と、それを使うプログラムです。

let fCont x cont = x / 2 |> cont
let gCont x cont = x + 10 |> cont
let hCont x cont = string x |> cont

let program () =
  fCont 42 (fun x ->
  gCont x (fun y ->
  hCont y (fun z ->
  printfn "%A" (x, y, z) )))

継続渡しスタイルの関数は、継続を末尾呼び出ししているのが一目で分かります。 では、継続渡しスタイルの関数を使っている側はどうでしょうか。 こちらも、それぞれの関数は末尾呼び出しになっています。 インデントを追加するとわかりやすいでしょう。

let program () =
  // fContの呼び出しは、program関数の末尾で行われている
  // gContなどの呼び出しは、関数でくるまれた中にいるその場では呼び出されない
  fCont 42 (fun x ->
    // gContの呼び出しは、fContの継続の末尾で行われている
    // hContなどの呼び出しは、関数でくるまれた中にいるのでその場では呼び出されない
    gCont x (fun y ->
      // hContの呼び出しは、gContの継続の末尾で行われている
      hCont y (fun z ->
        printfn "%A" (x, y, z)
      )
    )
  )

継続渡しスタイルの関数では、関数の最後は「継続を表す関数に結果を渡す」ことになりますし*5、 継続渡しスタイルの関数を呼び出す場合もやはり末尾呼び出しになります。 そのため、再帰部分を継続渡しスタイルで書けば自動的に末尾呼び出しになるのです。

つまり、末尾再帰ではない再帰関数をCPS変換したら末尾再帰関数になり、末尾呼び出しの最適化がかかります。 ようやく、CPS変換のうれしさが分かるところまで来ました。 では、末尾呼び出しになっていない再帰関数をCPS変換してみましょう。

階乗をCPS変換

簡単な例として、階乗からやってみます。 まずは、末尾再帰ではないfactの定義です。

let rec fact = function
| n when n = 0I -> 1I
| n -> n * (fact (n - 1I))

bigintが定数パターンとして使えないのでwhenを使っているのがちょっと残念ですが、それ以外は普通のコードです。 この関数は、再帰呼び出しをした後にその結果とnの値を掛けているため、末尾再帰になっていません。 そのため、この関数に50000Iを渡すとスタックオーバーフローが起きました。

これを、まずは再帰呼び出し部分をletを使った形に書き換えます。 letを使った形にするとCPS変換しやすくなるので、慣れないうちはまずはletを使った形に変形するところから始めるといいでしょう。

let rec fact n =
  if n = 0I then 1I
  else
    let pre = fact (n - 1I)
    n * pre

次に、これをCPSに書き換えます。 まずは、継続を引数contとして受け取るようにします。

(* 変換途中 *)
let rec fact' n cont =
  if n = 0I then 1I
  else
    let pre = fact' (n - 1I)
    n * pre

contは継続なので、fact'の処理の結果を渡してあげることでfact'の後ろの処理を実行します。 こうでしょうか？

(* 変換途中: elseがおかしい *)
let rec fact' n cont =
  if n = 0I then 1I |> cont
  else
    let pre = fact' (n - 1I)
    n * pre |> cont

これはコンパイルが通りません。 fact'は第二引数として継続を受け取るため、preはfact'の結果ではなく関数になってしまっています。 そこで、fact'を呼び出した後の処理(n * pre |> cont)をfact'に渡す無名関数の中に入れてしまいます。

(* 変換完了！ *)
let rec fact' n cont =
  if n = 0I then 1I |> cont
  else
    fact' (n - 1I) (fun pre ->
    n * pre |> cont)

letで導入される変数を無名関数の引数として導入する形にするのは、今まで何回か見てきているので大丈夫でしょう。 これで無事、CPS変換できました！ しかしこのままでは元の関数と同じ使い方ができません。 「スタックオーバーフローしなくなりましたが、代償として継続を渡す必要ができました！」では駄目でしょう。 そこで、CPSな関数をラップする関数を用意します。

CPS版のfact'をラップする

さて、fact'を外から呼び出す場合、contには何を渡せばいいでしょうか？ それを考える前に、fact'のシグネチャを確認してみましょう。

val fact' :
  n:System.Numerics.BigInteger ->
    cont:(System.Numerics.BigInteger -> 'a) -> 'a

System.Numerics.BigIntgerの別名としてbigintがあるので、これを使って書き直すと、

val fact' : n:bigint -> cont:(bigint -> 'a) -> 'a

こうです。 ここから分かるのは、

1. 継続を表す関数contには、fact'が計算した結果が渡される
2. 継続を表す関数contは、任意の結果型を返せる
3. 継続を表す関数contが返した型が、fact'全体の結果型になる

です。 1つ目は、今まで見てきた通りのことです。継続には結果が渡されます。 2つ目と3つ目に注目してください。 今まで、一番外側(一番深い部分)の継続では、printfnによる出力を行っていました。

fact' 5 (fun res ->
printfn "%d" res)

今まで通りならこんな感じです。 これを上の3つに当てはめてみると、

1. resにはfact'が計算した結果が入っている
2. printfn "%d" resはfact'が計算した結果を出力して、unitを返す
3. fact'に渡した継続がunitを返すので、fact'の呼び出し全体としてもunitを返す

となります。 ということは、CPS変換された関数から値を取り出すには、継続に渡された結果をそのまま返せばいいということになります。 これは、継続としてid関数を渡せばいい、ということですね。

let res = fact' 5 id
printfn "%d" res

つまりこれを関数化すれば、factのユーザは中でCPS変換された関数に実装が変わってもなにも気にしなくていいわけです。

let fact n = fact' n id

fact'を外から使わせないようにするために、関数内関数にしてもいいでしょう。

let fact n =
  let rec fact' n cont =
    if n = 0I then 1I |> cont
    else
      fact' (n - 1I) (fun pre ->
      n * pre |> cont)
  fact' n id

これで変換完了です。 実際にこれを試したい人は、プロジェクトのプロパティから「末尾呼び出しの生成」をオンにしてください(Releaseモードであればデフォルトでオンのはずです)。 また、fsiであれば設定不要で試せます。 この関数には、50000Iを渡してもスタックオーバーフローは起こしません。 CPS変換をしたことによって、末尾再帰になり、末尾呼び出しの最適化がかかったようです。

スタックオーバーフローするような再帰を書いてしまったときに、CPS変換を行えばスタックオーバーフローを回避できるようになります。 他にも回避する方法はあります*6が、 CPS変換は慣れてしまえばほとんど機械的に行えるので、自分の道具箱に入れておいてもいいでしょう。

その2はコンピュテーション式の話になる予定です。

おまけ

ここからはおまけです。もしくはボーナスステージ。 色々な関数をCPS変換してみましょう。

sum関数

オリジナル

let rec sum = function
| [] -> 0
| x::xs -> x + (sum xs)

letで書き換え

let rec sum xs =
  match xs with
  | [] -> 0
  | x::xs ->
      let pre = sum xs
      x + pre

CPS!

let rec sum xs cont =
  match xs with
  | [] -> 0 |> cont
  | x::xs ->
      sum xs (fun pre ->
      x + pre |> cont)

あ、id渡すラッパー関数は自明なので書きません。

max関数をCPS変換

オリジナル

let rec max = function
| [x] -> x
| x::xs ->
    let pre = max xs
    if pre < x then x
               else pre

letで書き換え

letで書き換え自体は不要だけど、functionをmatchにしておく。

let rec max xs =
  match xs with
  | [x] -> x
  | x::xs ->
      let pre = max xs
      if pre < x then x
                 else pre

CPS!

let rec max xs cont =
  match xs with
  | [x] -> x |> cont
  | x::xs ->
      max xs (fun pre ->
      if pre < x then x   |> cont
                 else pre |> cont)

find関数をCPS変換

オリジナル

let rec find pred = function
| [] -> failwith "not found."
| x::xs -> if pred x then x
                     else find pred xs

letで書き換え

let rec find pred xs =
  match xs with
  | [] -> failwith "not found."
  | x::xs ->
      if pred x then x
                else
                  let res = find pred xs
                  res

CPS!

let rec find pred xs cont =
  match xs with
  | [] -> failwith "not found."
  | x::xs ->
      if pred x then x |> cont
                else find pred xs cont (* (fun res -> res |> cont)なので、単にcontを渡せばいい *)

map関数をCPS変換

オリジナル

let rec map f = function
| [] -> []
| x::xs -> (f x) :: (map f xs)

letで書き換え

let rec map f xs =
  match xs with
  | [] -> []
  | x::xs ->
      let y = f x
      let ys = map f xs
      y::ys

CPS!

let rec map f xs cont =
  match xs with
  | [] -> [] |> cont
  | x::xs ->
      let y = f x
      map f xs (fun ys ->
      y::ys |> cont)

これは、map自体のCPS変換です。 fがCPS変換された関数の場合は、

let rec map f xs cont =
  match xs with
  | [] -> [] |> cont
  | x::xs ->
      f x (fun y ->
      map f xs (fun ys ->
      y::ys |> cont))

こうですね。

フィボナッチ関数をCPS変換

オリジナル

let rec fib = function
| 0 | 1 -> 1
| n -> fib (n - 1) + fib (n - 2)

letで書き換え

let rec fib n =
  match n with
  | 0 | 1 -> 1
  | n ->
      let pre1 = fib (n - 1)
      let pre2 = fib (n - 2)
      pre1 + pre2

CPS!

let rec fib n cont =
  match n with
  | 0 | 1 -> 1 |> cont
  | n ->
      fib (n - 1) (fun pre1 ->
      fib (n - 2) (fun pre2 ->
      pre1 + pre2 |> cont))

*1:contはcontinuationの略です。継続を表す変数名には他にもkなどが使われたりします。

*2:再帰関数のことを扱う場合が多いですが、再帰関数でなくとも末尾呼び出しと言えます。

*3:自分自身のスタックを再利用したり、ループに変形したりというやり方もありますが、どの方法でもスタックを消費しないという効果は同じです。

*4:他にも、Chain of Responsibilityパターンを適用した際に大量のオブジェクトがchainを構成する場合など、再帰しない場合でもうれしい場面はあります。

*5:例外を投げるとか、継続を捨てるとかは無視します。

*6:アキュムレータ変数を使う方法や、ループに書き換える方法などが使えます。

なごやかJava ゆるふわテストツール編で発表してきた

テストの自動化を考える前に from bleis tift

発表してきました。

テストツール編なのに、Javaにもテストツールにも関係のない、テスト自体の話です。 それなりに反応は良かったかな？

資料作ってる時に、盛り込み過ぎだったので資料から抜いたものを独立して別の資料にしたので、時間があったらそっちも発表しようかなー、と思っていたんですが、なかったので公開だけしておきます。

効果の低いテストの話 from bleis tift

異論は認める。

2つのOptionalで分岐する

僕のOptional<>の使い方がカッコワルイ。 - 谷本 心 in せろ部屋にある最後の例ですが、 2つのOptionalの組み合わせによって処理を分岐させるコードが幾つか載っています。 ifで書いた例を見てみましょう。

public String hello(Optional<String> name1, Optional<String> name2) {
    if (name1.isPresent()) {
        if (name2.isPresent()) {
            return call(name1.get(), name2.get());
        } else {
            return call1(name1.get());
        }
    } else {
        if (name2.isPresent()) {
            return call2(name2.get());
        } else {
            return call();
        }
    }
}

まとめると、こんな感じでしょうか。

name1	name2	呼び出すメソッド
値有り	値有り	2引数call
値有り	Empty	call1
Empty	値有り	call2
Empty	Empty	0引数call

これ、F#だったらmatch式を使えば分かりやすく書けます。

let hello name1 name2 =
  match name1, name2 with
  | Some name1, Some name2 -> call(name1, name2)
  | Some name1, None -> call1(name1)
  | None, Some name2 -> call2(name2)
  | None, None -> call()

JavaのOptionalにもしmatchメソッドが実装されていれば、こんな感じに書けるんですけどね。

public String hello(Optional<String> name1, Optional<String> name2) {
    return name1.match(
        n1 -> name2.match(n2 -> call(n1, n2), () -> call1(n1)),
        () -> name2.match(n2 -> call2(n2), () -> call())
    );
}

Optionalのような型を導入するのであれば、やはりmatch式のようなもの*1が欲しくなりますね、という話でした。

*1:あとついでにモナド用の構文も・・・

Effective Visual F# Power Tools

さてさて、またもや他人のAdvent Calendarに乗っかったネタです。 今日は、Visual F# Power Tools の紹介というF# Advent Calendar 2014の11日目の記事です。

VFPTの基本的な便利な機能は元記事を参照いただくとして、このエントリでは更に進んだ使い方等を紹介します。

シンタックスのカラーリングのカスタマイズ

シンタックスのカラーリングはカスタマイズできます。 カスタマイズは、VS自体のオプションの左のペインから環境、フォントおよび色と選択し、 表示項目のF#から始まる項目です。

カスタマイズできる項目は以下の通りです。

• F# Escaped Characters
• F# Functions / Methods
• F# Modules
• F# Mutable Variables / Reference Cells
• F# Patterns
• F# Printf Format
• F# Quotations
• F# Types
• F# Value Types

この中でおすすめなのが、「F# Mutable Variables / Reference Cells」です。 これを設定することで、mutableな変数やref型の変数に色が付き、どこで再代入を使っているかが一目瞭然になります。

スコープもちゃんと認識していますね。 ちなみに、setterがあるプロパティなんかも、Mutable Variablesとみなされて色が付きます。

他には、「F# Escaped Characters」と「F# Printf Format」も便利です。 上のコードでも、printf系の関数のフォーマットに色が付いているのが分かります。 「F# Quotations」も人によっては便利でしょう。 「F# Patterns」は、便利かどうかは微妙ですが、設定してあります。

SomeとNoneに色がついているのや、自動実装プロパティのFailedに色がついているのが分かります。

自動実装とタスクリストコメント

元記事ではインターフェイスの自動実装と判別共用体ケースの自動実装に触れられていますが、もう一つ、レコードのスタブ生成機能もあります。 これら自動実装系の機能と、タスクリストコメント*1を合わせる技をadacolaさんが呟いています。

Visual F# Power ToolsのCode GenerationをUncompilable Codeにして内容を(* TODO 自動生成のまま未実装 *)みたいにしておくと、タスク一覧で自動生成したままの箇所が一覧できてよさげ

— adaco (@adacola) November 8, 2014

これは是非設定しておくといいでしょう。

failwith "oops!" (* TODO : Not implemented yet *)

このように設定しておけば、(Uncompilable Codeと言いつつ)コンパイル可能で、かつタスク一覧に「TODO : Not implemented yet」と表示されるようになります。

便利！

その他の機能

元記事では触れられていない機能をざっくり紹介します。

ドキュメンテーションコメントの自動生成

///<までタイプするとドキュメンテーションコメントのひな形を生成してくれます。 地味ですが、ドキュメンテーションコメントを書くときに便利です。

VFPTとは関係ありませんが、F#ではドキュメンテーションコメントの中身がsummaryだけであれば、summaryを省略できるという便利機能があります。

/// とても素晴らしい変数です。
let x = 42

これも知っていると便利なので使っていきましょう。

ソースコードの整形

整形してくれます。あんまり使ったことはありません。

もちろん、VSの整形のショートカットで呼び出せます。 使う人は使う機能かも？

ナビゲーションバー

便利機能です。この機能を有効にするには、VSを管理者権限で立ち上げてから「Navigation bar」のチェックボックスをチェックし、VSを再起動する必要がありますので注意してください*2。

この機能を有効にすると、エディタの上にナビゲーションバーが表れて、選択した型やメンバに簡単にジャンプできるようになります。 上の画像で、「Program」とか「g」とか表示されているのが分かります。

参照箇所のハイライト

便利機能です。カーソルを置いている変数や関数と同じものを参照している箇所をハイライトしてくれます。

インデントガイド/Depth colorizer

便利機能です。F#はインデントに意味のある言語なので、インデントガイドを出してくれると色々と捗ります。

上の画像でも、インデントガイドが確認できます。

NavigateTo

便利機能です。Ctrlキーを押しながらカンマキーを押すと起動できます。 起動したら、型名とか関数名とか適当にタイプしてみてください。そういうことです。

フォルダ機能

最近使ってません。 プロジェクトが巨大になればお世話になることでしょう。

openしていない名前空間の解決

便利機能です。Hogeを含むモジュールがあった時に、Hoge.piyoとかやってHogeまでカーソルを持っていくと、スマートタグが表れるのでCtrl+.で起動してEnterです。

未使用宣言のグレーアウト

使っていない変数や関数などをグレーアウトしてくれます。 不安定なので現状ではOffにしておくといいでしょう。 次のバージョンではもうちょっと改善される予定です。

未使用openのグレーアウト

使っていないopenをグレーアウトしてくれます。 不安定なので現状ではOffにしておくといいでしょう。 次のバージョンではもうちょっと改善される予定です。

メタデータに移動

便利機能です。ソースを持っていないコードのシグネチャ等を確認する際、この機能がない時代はオブジェクトブラウザを使ったりしていましたが、F12で確認できるようになりました。

タスクリストコメント

便利機能です。この機能は実装にも関わったので、思い入れもある機能です。 タスク一覧ウィンドウを開いて、(ユーザー タスクではなく)「コメント」を選ぶと、TODOコメントなどが一覧できます。

オプションからカスタマイズ可能で、「環境」、「タスク一覧」と辿ると設定画面になります。 「名前」の欄に「XXX」とか入れて、追加ボタンを押すとトークンリストに追加されます。 このUIは非常にわかりにくいと思うんですが、まぁVS標準の機能だし仕方ない。

VFPTの今後

次のバージョン

次のバージョンでは、細かい点が修正され、目立った新機能は追加されないようです。

• New folderダイアログがリストアされない問題を修正
• 大きなソリューションでの「全ての参照の検索」機能のパフォーマンスを改善
• Goto Metadataで表示されるコードにエラーが表示される問題のいくつかを修正
• これ以上自動生成するものがないスマートタグを表示しないように変更
• printf系関数のフォーマットの色付けをユーザ定義のものまで拡張
• ソースが存在する構造体への移動がメタデータへの移動になる問題を修正

今後載るかもしれない機能

コメントの折り畳み機能がもしかしたら載るかもしれないです。

機能追加の要望方法

GithubのIssuesではなく、VFPTのUser Voiceに投稿してください。 Voteもできるので、気になった機能があればVoteするといいでしょう。 幾つかピックアップして紹介します。

クラスビューでのコードナビゲーション

Feaure Request: Code Navigation Using Class View で提案されています。

ナビゲーションバーは一つのファイルであれば便利だけど、クラスビューであればプロジェクト全体をナビゲートできて便利だよね、という提案です。

ローカルで閉じたIDisposableでletを使っていた場合にuseを使うよう提案

Suggest to use use instead of let for local IDisposable valuesで提案されています。

IDisposableを実装した型にletを使っていた場合、それをuseを使うように提案してくれるような機能の提案です。 実装されれば有用そうですが、ローカルで閉じているかどうかのチェックって簡単にできるんでしょうか・・・

式の型の表示

Show type annotation on expressionで提案されています。

Scala-plugin for Intellij ideaで実装されている機能のようですね。 あると便利なのは間違いないでしょう。

推論された型の表示

Display inferred types above declarationで提案されています。

コンパイラによって推論された型を、定義の上に(CodeLensのように)表示する機能の提案です。 コメントでは結構散々な言われようですが、これ、実装されればめちゃくちゃ便利だと思うんですよ。

CodeLens APIが公開されていないようなので、CodeLensっぽくできるかどうかわからないかつ、公開されたとしても関数内関数は結局自作になりそうなので、全部自作してしまえばいいじゃん、と思うんですが果たして。 エディタ上にCodeLensのように行じゃない行(?)を差し込めるのかどうかが問題だと思うんですが、教えてVS拡張に詳しい人！

まとめ

VFPTを使いこなして楽しくF#でプログラミングしましょう！

*1:これも実はVFPTの機能で、生のVSだとF#でタスクリストすら使えません。

*2:再起動自体はほかの機能も必要ですが、管理者権限でVSを立ち上げる必要があるのはこの機能のみです

コンピュテーション式の変形後を覗き見るを改良する

さてさて、気になるネタがまた増えたようです。 コンピュテーション式の変形後を覗き見るというエントリがF# Advent Calendar 2014の10日目の記事として公開されました。 Quoteを差し込んで、Runで表示する、というのは面白いアイディアですね。

だが俺の前でコンピュテーション式の変換を扱ったのが運の尽きだ！ 添削をくらうがいい！

・・・同僚だからってやりたい放題ですね。

変換に必要なメソッド

変換対象が

let ret = simple {
  let x = 10
  return x
}

程度であれば、必要なメソッドはReturnだけです。 BindもReturnFromも不要です。

ですが、消してしまってはあまりにも単純なので、 Bindを使う例を扱えるようにしましょう！

変換対象はこうなります。

let res = simple {
  let! x = 10
  return x
}

このコードがコンパイルできるようにするために必要なコンピュテーションビルダーの定義はこれです。

type SimpleBuilder () =
  member __.Return(x) = x
  member __.Bind(x, f) = f x

let simple = SimpleBuilder ()

手動で変換する

では、このコードを変換していきます。

let res = simple {
  let! x = 10
  return x
}

一番外側はいいでしょう。

let res =
  let b = simple in
  {| let! x = 10 in return x |}

let!の変換

{|と|}に挟まれた部分(cexpr)がlet! ...という形をしているので、 let!の変換規則を最初に適用します。

let b = simple in
T(return x, fun v -> C(b.Bind(10, fun x -> v)))

Bindの呼び出しが出てきました。

returnの変換

Tの最初の引数(変換対象)がreturn xという形をしているので、 returnの変換規則を適用します。

let b = simple in
b.Bind(10, fun x -> b.Return(x))

Returnの呼び出しが出てきました。 これ以上変換すべき個所はありませんので、手動変換はここまでです。 ビルダーにはBindもReturnも適切に定義されているため、コンパイル可能です。

変換を出力する

さて、元の記事ではSimpleBuilderを弄って変換の様子を出力するようにしていました。 同じ方法だと面白くないので、この記事では別の方法を取ってみることにします。 その前に、Quoteについて突っ込んでおきます。

Quote変換

Quoteは元記事でも使っていますが、その定義は

member this.Quote(x) = x

と、あたかも式木がxとして渡されてそれをそのまま返しているように見えます。 しかし、実際はQuoteメソッドは呼び出されることはありません。 ただ単に、Quoteという名前で定義されてさえいればいいのです。 そのため、紛らわしさを無くす意味でもQuoteの実装は、

member __.Quote() = ()

としておいた方がいいと思います。

コンピュテーションビルダーに機能を後付けする

さて、コンピュテーションビルダーに対する機能の追加ですが、方法としては以下のものがあるでしょう。

1. コンピュテーションビルダーの書き換え
2. 既存のコンピュテーションビルダーを継承して機能を追加
3. 型拡張として機能を追加
4. 拡張メソッドとして機能を追加

1つ目の方法が元記事のやり方です。 一番シンプルですが、コードがない場合にはこの方法は選べません。

2つ目の方法は、面倒ですしそれほど説明すべき点もないので省略します。

3つ目と4つ目の方法を今回紹介します。

型拡張として機能を追加

コンピュテーション式の変換は、コードの表現しか見ておらず、 実現方法は問題にしていません*1。 そのため、ビルダーに対してメソッドを呼び出せるようになっていれば、 コンピュテーションビルダーにメソッドが定義されている必要はありません。

型拡張でQuote機能を追加する例を見てみましょう。

open FSharp.Quotations.Evaluator

type SimpleBuilder with
  member __.Quote () = ()
  member __.Run(expr: Quotations.Expr<_>) =
    // ここにexprを出力するコードを書く

    // 式木を実行するために、FSharp.Quotations.Evaluatorを使用
    expr.Evaluate()

この型拡張を適当なモジュールに入れ、 そのモジュールをopenするかどうかでexprを出力するかどうかを切り替えれるようになります。 しかし、ビルダーにQuoteメソッドを追加してRunの引数の型をExpr<_>型にしてしまい、 Runメソッドの中で引数をそのまま返してしまうと、 コンピュテーション式利用側はExpr<_>を受け取ることになってしまいます。 これでは、元のコードをコンパイルできなくなってしまいます。

そこで、FSharp.Quotations.Evaluatorというライブラリを使います。 このライブラリは、F#のコードクォートを実行するためのライブラリです。 Runメソッドの最後でEvaluateを呼び出し、 QuoteでExpr<_>にしたものをまた戻します*2。

拡張メソッドとして機能を追加

型拡張ではなく、もちろん拡張メソッドとして定義することもできます。

open System.Runtime.CompilerServices
open FSharp.Quotations.Evaluator

[<Extension>]
type SimpleBuilderExtension private () =
  [<Extension>]
  static member Quote (_: SimpleBuilder) = ()
  [<Extension>]
  static member Run(_: SimpleBuilder, expr: Quotations.Expr<_>) =
    // ここにexprを出力するコードを書く

    // 式木を実行するために、FSharp.Quotations.Evaluatorを使用
    expr.Evaluate()

少々面倒なので、型拡張でいいですね。 一応、できるということで。

exprを出力するコード

少し改良していますが、基本的には元の記事と同じです。

open Microsoft.FSharp.Quotations.Patterns
open System.Collections.Generic

module Printer =
  let mutable private i = 0
  let private valueMap = Dictionary<obj, string>()
  let printKnownVar obj =
    if obj = box simple then
      "simple"
    else
      "unknown_var"
  let printValues () =
    valueMap
    |> Seq.sortBy (fun kv -> kv.Value.Substring(2) |> int)
    |> Seq.map (fun kv -> sprintf "let %s: %s = %s" kv.Value (kv.Key.GetType().Name) (printKnownVar kv.Key))
  let rec print (expr: Quotations.Expr) =
    match expr with
    | Call (Some receiver, m, args) ->
        (* インスタンスメソッド呼び出しを文字列化 *)
        let receiver = print receiver
        let args = List.map print args |> String.concat ", " (* reduceじゃなくてconcatでOK *)
        sprintf "%s.%s(%s)" receiver m.Name args
    | Value (obj, typ) ->
        (* 値を文字列化 *)
        if typ = typeof<SimpleBuilder> then
          (* 値が辞書にあったらそれを変数として扱うように変更 *)
          match valueMap.TryGetValue(obj) with
          | true, name -> name
          | false, _ ->
              let name = sprintf "$b%d" i
              i <- i + 1
              valueMap.Add(obj, name)
              name
        else
          string obj
    | Lambda (arg, Let(var, value, body)) when arg.Name = print value ->
        (* 単純なラムダ式を文字列化 *)
        (* Expr<_>の表現力の問題によって、Lambdaではラムダ式すべてを表現できない。
           例えば、ラムダ式の引数部分でパターンマッチできるが、
           Expr<_>のLambdaはargがVarなので、Letと組み合わせることでこれを再現している模様。 *)
        let arg = var.Name
        let body = print body
        sprintf "(fun %s -> %s)" arg body
    | Var v ->
        (* 変数を文字列化 *)
        v.Name
    | _ ->
        (* 対応できない式木はエラーにするように変更 *)
        failwithf "%A is not supported." expr

type SimpleBuilder with
  member __.Quote () = ()
  member __.Run(expr: Quotations.Expr<_>) =
    let exprStr = Printer.print expr
    let values = Printer.printValues ()
    values |> Seq.iter (printfn "%s")
    printfn "%s" exprStr
    expr.Evaluate()

改良した点としては、

• 変数を出力するようにした
• 実装を洗練
• Runの結果を変えないように、式木を実行するようにした

というところです。

実行してみる

拡張を施したモジュールをopenすると、既存のコンピュテーション式の挙動が変わり、 Printer.printの結果が出力されるようになります。

let res = simple {
  let! x = 10
  return x
}

このコードを実行してみると、このような出力が得られます。

let $b0: SimpleBuilder = simple
$b0.Bind(10, (fun x -> $b0.Return(x)))

結果比較

手動変換した結果はこうでした。

let b = simple in
b.Bind(10, fun x -> b.Return(x))

そして、QuoteによってExpr<_>にしたものを文字列化したのがこれです。

let $b0: SimpleBuilder = simple
$b0.Bind(10, (fun x -> $b0.Return(x)))

完全に一致！！！

まとめ

コンピュテーション式がどんな風に変換されるのか見るために、 Quoteで式木化してF#コードに文字列化するのはいいアイディアでした。 この記事では、以下のことをやりました。

• Bindを必要な例に変更
• 既存のコンピュテーションビルダーに機能を追加する方法
• 出力されるコードに何も手を加えなくても手動変換の結果とほとんど同じになるようなExpr<_>の出力

Expr<_>の限界*3はありますが、 これを推し進めれば、かなり良い感じに色々なコンピュテーション式の変換結果を出力できるようになりそうです。

今年もF# Advent Calendarは豊作ですね！素晴らしいです。

*1:ダックタイピング的、とも言えるでしょう。

*2:Delayを定義している場合は、更にユニットを渡す必要があります。

*3:match式がIfThenElseに落ちるなど

クラスのコンストラクタ呼び出し時にプロパティも同時に初期化する

これはF# Advent Calendar 2014の9日目の記事(ピンチヒッター)です。 昨日の記事はねのさんによるFSharperならこう書く(A Poker Game Program) #FsAdventでした。 この記事を勝手に添削したエントリも、よろしければ合わせてどうぞ。 何度も言いますが、コードが読みやすくて書き換えが大変楽でした。

さて、今日はF# のネタリストから、クラスのコンストラクタ呼び出し時にプロパティも同時に初期化する方法です。 Advent Calendarのネタに困っている人は、参考にしてみるといいかもしれません。

F#のプロパティ

F#のプロパティの定義は、複数の書き方があります。 C#の自動実装プロパティに初期値を持たせた書き方もサポートしていますので、今回はそれを使いましょう。

type Class(x: int) =
  member val Name = "" with get, set

これで、C#での

public class Class
{
    readonly int x;
    public string Name { get; set; }

    public Class(int x)
    {
        this.x = x;
        this.Name = "";
    }
}

に大体対応します。ヤバい短さですね。

コンストラクタ呼び出し時にプロパティも同時に初期化したい

上のように作ったクラスを生成する際に、C#ではオブジェクト初期化子という構文を使って、プロパティも同時に設定できます。

var c = new Class(10) { Name = "hoge" };

便利ですね！ 実は(?)、これと同じことがF#でもできます。

let c = Class(10, Name="hoge")

これだけです！

これは、F#での名前付き引数とまったく同じ構文ですね。 なので、当然(?)これらは混ぜることができます。

let c1 = Class(x=10, Name="hoge")
let c2 = Class(Name="hoge", x=10)

素晴らしい！

本日は以上です。 明日は、ざっきーさんの番ですね！

Re: FSharperならこう書く(A Poker Game Program) #FsAdvent

FSharperならこう書く(A Poker Game Program) #FsAdventというエントリがF# Advent Calendar 2014の8日目の記事として公開されました。 この記事自体は、主に設計よりな話をしていますが、ここでは実装寄りの話を中心に、 勝手に添削してみました。 また、記事の中に書かれていた疑問にも回答したりしています。

添削その1(全体)

型とモジュールの名前

元のコードでは、モジュールの中にTという型を入れるスタイルのようです。

(* 柄 *)
module Suit =
    (* 柄 *)
    type T = | Spade | Heart | Diamond | Club
    (* 全ての柄 *)
    let values = [Spade; Heart; Diamond; Club]

自分も昔はこんな感じにしていたのですが、現在のところこのスタイルはやめ、モジュール名と型名に同じ名前を付けるスタイルを採用しています。

type Suit = Spade | Heart | Diamond | Club

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Suit =
  let values = [Spade; Heart; Diamond; Club]

なんでかというと、

• F#には高度なモジュールシステムがないので、あまり意味がない
• 同じ型名が(モジュールが別だとしても)複数あると、複数型推論が微妙になる

あたりが大きな理由です。 CompilationRepresentationとかCompilationRepresentationFlags.ModuleSuffixとか面倒ですが、覚えてしまえばどうということはないですよ。

回答その1(Card)

レコード生成の制限

こんな疑問が書かれていました。

番号は、1から13に含まれない値は生成できないようにしたいので、classになりそうです。 classにするとinterfaceの実装が煩わしいところですが、constructorを制限しようと思うと、レコードや判別共用体では厳しそうです。 もし他に良い方法をご存知の方がいらっしゃったら教えてください。

これに対する回答としては、2通りあります。

• シグネチャファイルで型の実装を隠蔽する
• privateで型の実装を隠蔽する

前者はfsiファイルを書かなければならず、面倒というのと、型の実装を隠蔽してしまうとcomparison制約とかも自分でやる必要が出てきてそれも面倒なので、今回はお手軽にprivateで隠蔽する方法を紹介します。 元のコードはこんな感じです。

(* 番号 *)
module Number =
    type T(value:int)=
        do
            (* 数値範囲チェック *)
            if not (min <= value && value <= max)
                then failwith "The Number is required 1 to 13."

これを、型名を変更しつつレコードで実現してみましょう。

type Number = private {
  Value: int
}

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Number =
  let min = 1
  let max = 13
  let value x = x.Value
  let create x =
    (* 数値範囲チェックをこちらに書く *)
    if not (min <= x && x <= max) then
      failwith "The Number is required 1 to 13."
    { Value = x }

こうすることによって、それを含むモジュール(ここではファイルと思ってください)の外からは{ Value = 42 }のようには書けなくなりますし、当然let f (x: Number) = x.Valueというコードもコンパイルエラーになります。 パターンマッチも(それを含むモジュールの外では)できなくなるので注意してくださいね。

IComparable

レコードにしたため、IComparable等の実装が不要になりましたが、元のバージョンではこれらを実装していました。 さて、これらを実装しているのはいいのですが、実は大小比較だけしたいだけであれば実装するインターフェイスはかなり減らせます。

type T(value: int) =
  (* snip *)
  member this.Value = value
  interface System.IComparable with
    member this.CompareTo(other) =
      match other with
      | :? T as x -> compare value x.Value
      | _ -> failwith "other is not T"
  (* snip *)

これだけで、警告は出るものの=も<も他の比較演算子も使えるクラスになります。 このあたりは、言語仕様(PDF)の8.15.3を参照してください。 ざっくり説明すると、System.IComparableを明示的に実装している場合、Equalsメソッドは

override x.Equals(y : obj) =
  ((x :> System.IComparable).CompareTo(y) = 0)

という実装が生成されるという感じです。 CompareToはジェネリック版ではなく非ジェネリック版が呼び出されるので、System.IComparableだけ実装すればよい、ということですね。 また、compare関数を使えばCompareToメソッドは簡単に実装できます。

ただし、これに頼る場合は警告が出るみたいです。言語仕様にはその記述はなかったように思いますが・・・

添削その2(Deck)

単純なfor式

山札を表すDeckモジュールのdeck_without_joker関数ですが、一番内側のfor式はyieldしか含みません。

(* デッキ(ジョーカー抜き) *)
let deck_without_joker = List.ofSeq(seq{
        (* シーケンス式の二重ループでNumberとSuitの組み合わせを列挙する *)
        for num in Card.Number.min .. Card.Number.max do
        for suit in Card.Suit.values do
            yield { Card.Number = Card.Number.create num; Card.Suit = suit }
    })

このような場合、do yieldの代わりに->が使えます。 名前もlikeThis形式に変えておきましょう。

let deckWithoutJoker =
  List.ofSeq (seq {
    for num in Card.Number.min .. Card.Number.max do
    for suit in Card.Suit.values ->
      { Card.Number = Card.Number.create num; Card.Suit = suit }
  })

添削その3(List)

take関数の名前

既存のListモジュールに足りない処理を追加するために、独自のListモジュールを作っています。 その中で、takeという関数を追加しているんですが、これは標準のtakeを隠してしまううえ、やっていることもtakeではない気がします。

やっていることは、countでのリストの分割ですので、splitAtがいいでしょう。 名前は、Hoogleで探しました。 また、optionを返す関数はF#ではtryプレフィックスを付けるのが慣習ですので、trySplitAtとしてみました。

let trySplitAt count list =
  let rec loop i acc tail =
    if i = count then Some ((List.rev acc), tail)
    else match tail with
         | [] -> None
         | h::t -> loop (i + 1) (h::acc) t
  loop 0 [] list

tail |> functionとしている部分は、好みもありますが、個人的にはmatch tail withの方が好きなのでその部分も変更してあります。

また、Deck.pickもoptionを返すので、Deck.tryPickにしました。

回答その2(Hand)

単一ラベルの判別共用体

こんな疑問がありました。

単一ラベルの判別共用体ってどうなのでしょうか。

これは、ありだと思います。 FsControlを使うと、単一ラベルの判別共用体を多用するようになります(そうじゃない)。

添削その4(Hand)

System.String.Join

.NETの便利関数にSystem.String.Joinというのがあるのですが、 これはBasis.CoreのStr.joinを使いましょう。 嘘です。Stringモジュールのconcat関数を使いましょう。

ToString

ToStringの呼び出しは面倒なので、string関数を使いましょう。 コードは2つ下を見てください。

List.toArray呼び出し

String.concatは'T seqを受け取り、'T listは'T seqなのでtoArrayする必要はありません。 コードは1つ下を見てください。

逆向きパイプライン演算子

ToStringの実装で、逆向きのパイプライン演算子を使っています。

(* CUIの選択肢表示用ToString *)
member this.ToString indexes = this |> function
    | Hand xs -> 
        xs
            |> List.map2 (fun x y ->
                    sprintf "[%s]:%s" y (x.ToString())
                ) <| indexes (* 逆向きパイプライン演算子<|はロマン *)
            |> List.toArray
            |> curry System.String.Join "/"

ここは、||>の出番です。

member this.ToString indexes =
  match this with
  | Hand xs ->
      (xs, indexes)
      ||> List.map2 (fun x y -> sprintf "[%s]:%s" y (string x))
      |> String.concat "/"

あ、curry関数は使わなくなったので削除しました。

引数の位置でのパターンマッチ

createBy関数やchange関数で、レコードや判別共用体のパターンマッチをしている部分が何か所かあります。

(* 山札から最初のcount枚を取得して手札を作り、残りの山札とペアにして返す。
  山札の枚数が足りない場合はNone
*)
let createBy deck =
    Deck.pick count deck
        |> Option.map (fun pickResult -> 
            (* let束縛のレコードパターン *)
            let { Deck.Picked = picked; Deck.Deck = d } = pickResult
            ((Hand picked), d)
        )

(* 手札のうちchangeCardsで指定されたカードを捨て、山札から同じ枚数を加え、残りの山札とペアにして返す。 *)
let change hand deck changeCards =
    Deck.pick (Set.count changeCards) deck
        |> Option.map (fun pickResult ->
            let { Deck.Picked = picked; Deck.Deck = d } = pickResult
            let hand = hand |> function
                | Hand xs -> xs |> List.filter (changeCards.Contains>>not)
            Hand (List.append picked hand), d
        )

これらは、引数の位置でパターンマッチすればいいので、こう書き直せます。

let tryCreateBy deck =
  Deck.tryPick count deck
  |> Option.map (fun { Deck.Picked = picked; Deck.Deck = d } -> ((Hand picked), d))
                  (* ↑ラムダ式の引数の位置でレコードを分解 *)

        (* ↓関数の引数の位置で判別共用体を分解 *)
let change (Hand xs) deck changeCards =
  Deck.tryPick (Set.count changeCards) deck
  |> Option.map (fun { Deck.Picked = picked; Deck.Deck = d } ->
                  (* ↑ラムダ式の引数の位置でレコードを分解 *)
      let hand = xs |> List.filter (changeCards.Contains >> not)
      Hand (List.append picked hand), d
  )

添削その5(Rank of Hands)

役の強弱

F#の話ではないですが、役の強弱がおかしい気がしますね。 一般的なルールに従って、修正します。

type Rank =
  | OnePair | TwoPair | ThreeCards | Straight
  | Flush | FullHouse | FourCards | StraightFlush | RoyalStraightFlush

型の別名

役判定関数モジュールで、Card.NormalCard arrayという型名を大量に使っています。 こういう場合、型略称を定義してしまうと楽でしょう。

type private Cards = Card.NormalCard array

pairwise

straightやflushの判定に、前のカードと今のカードをペアにしたシーケンスを得るために、

xs
    |> Seq.ofArray
    |> (fun xs -> Seq.zip xs (Seq.skip 1 xs))
    |> Seq.forall (fun t -> (fst t).Number ++ 1 = (snd t).Number)

というコードが出てきます。 これは、Seq.pairwiseというそのままな関数があるので置き換えてしまいましょう。

cards
|> Seq.pairwise
|> Seq.forall (fun t -> (fst t).Number ++ 1 = (snd t).Number)

タプルを引数の位置で分解する

上のコードはラムダ式の中でfstとsndを使っているので、これを引数の位置でのパターンマッチにしてしまいましょう。

cards
|> Seq.pairwise
|> Seq.forall (fun (x, y) -> x.Number ++ 1 = y.Number)

配列 vs リスト

型略称を用意したCardsは現在、配列です。 リストではなく配列にしたのは、

引数の型を配列にしたのは、インデックスでのアクセスが多そうだったから、という程度の理由です。

とありました。 しかし、リストでもインデックスでアクセスできるうえ、引数として渡される配列もしくはリストの要素数は、5です。 この部分がクリティカルに効いてくるとは思えないので、リストに変更しました。

type private Cards = Card.NormalCard list

もし問題が起こったら、この型略称の部分を戻して、呼び出し部分の型を変えればいいでしょう。

SequenceEqual

royalStraightFlushの判定で、System.Linq.Enumerable.SequenceEqualを使って判定していますが、 Listをそのまま扱えば=で比較できるので、変更してしまいましょう。

let royalStraightFlush (cards: Cards) =
  (straightFlush cards) && (
    let royal = [10..13]@[1]
    (cards |> List.map (fun x -> x.Number |> Card.Number.value)) = royal
  )

List.filter Option.isSomeしてList.map Option.get

Evaluator.evaluate等の関数で、List.filter Option.isSomeしてからList.map Option.getしている箇所があります。

evals
    |> List.map (fun f -> f x)
    |> List.filter Option.isSome
    |> List.map Option.get

こういった処理には、List.chooseという関数が使えます。

evals
|> List.map (fun f -> f x)
|> List.choose id

回答その3(Rank of Hands)

判別共用体の大小

判別共用体の大小に関して、

大小比較が定義順に依存するのはちょっとしたポイントです。ソースは忘れました。

とありました。 言語仕様を参照してみると、8.15.4に、

If T is a union type, invoke Microsoft.FSharp.Core.Operators.compare first on the index of the union cases for the two values, and then on each corresponding field pair of x and y for the data carried by the union case. Return the first non-zero result.

とあります。

• 2つの値の共用体ケースのインデックスがMicrosoft.FSharp.Core.Operators.compareに渡される
• 付随するデータがある場合、それらがMicrosoft.FSharp.Core.Operators.compareに渡される
• 0ではない最初の値が返される

ということのようですね。 共用体ケースのインデックスは、定義順に振られる*1ため、大小比較が定義順に依存するのです。

添削その6(メイン処理)

リストの生成

input_choicesの生成に、リストリテラルを使っています。

let input_choices = ["a"; "b"; "c"; "d"; "e"]

好みはわかれるかもしれませんが、ここは

let inputChoices = ['a'..'e'] |> List.map string

のように、文字のリストを..で作ってから文字列化したほうが楽な気がします。

まとめ

テストとかしてない*2ので動くかどうかわからないですが、コード全体はGistに上げました。

元のコードがとても読みやすく素晴らしかったです。 引き続き、F# Advent Calendarをお楽しみください！

*1:言語仕様の8.5.4にTagsというネストした型が作られ、0から始まる整数定数が振られる、というようなことが書いてあります

*2:元のコードを書き換えていっただけ。変換の過程でバグが入った可能性は大。