F# で汎用の関数(汎用のリテラル)を書く

F# FSharp

F# の整数は int(32ビット整数), int64(64ビット整数), bigint(多倍長整数) があって、もちろんそれぞれ型が違う。
ベキ乗とか階乗とか、どの整数型でも同じことをしたいだけでも、普通に書いたらそれぞれ実装しないといけない。


ところで F# には自動汎化という仕組みがあって、要は型を制限しないように書けば、互換性のあるどの型でも使える関数ができる。
「型安全なダックタイピング」と言っておけば、かっこいい。

let max a b = if a > b then a else b

let x  = max 1  2  // int
let xL = max 1L 2L // int64
let xI = max 1I 2I // bigint


自動汎化がうまくいっているかは、Visual Studio でソースを書いて、関数名にマウスを重ねれば確かめられる。


http://giovedi.net/img/fsharp1.png


型として 'a のように表示されれば、汎化が働いていることがわかる。
関数や変数にマウスオーバーすれば推論された型情報が表示されるのは「型推論＋IDEって最強！」と思わせてくれる。Haskell や OCaml の人に自慢しよう。


話を元に戻す。こちらは同じ方法ではうまくいかない。

let add a b = a + b


http://giovedi.net/img/fsharp2.png


型が 'a などではなく int になってしまっている。


MSDN の「インライン関数」の「インライン関数と型の推論」のところに少し説明がある。

inline がある場合は、型の推論に影響します。これは、インライン関数では静的に解決される型パラメーターを使用できるためです。これに対し、インライン関数以外では、このような型パラメーターを使用できません。
(中略)
inline 修飾子がない場合は、型の推論によって指定の型が関数に適用されます。この場合は int です。


というわけで、 inline を指定すればうまくいく。*1

let inline add a b = a + b


http://giovedi.net/img/fsharp3.png


ベキ乗や階乗を汎用的に書くには、まだもう一工夫いる。

let inline (^) x y  =
    if y = 0 then 1
    elif y = 1 then x
    else {2..y} |> Seq.fold (fun z _-> z*x) x

let inline factorial n =
    if n <= 0 then 1 
    else Seq.reduce (*) {1..n}


http://giovedi.net/img/fsharp4.png


リテラルの 0 や 1 によって，パラメータが int に推論されてしまっている。
int64 で使いたいときは 0L や 1L に置き換える……なんてことはしなくてすむにはどうしたらいいか。


とても原始的な対策として、「パラメータから 0 や 1 を作る」という手がある。

let inline (^) x y  =
    if y = 0 then x/x  // 1 を x/x に置き換え
    elif y = 1 then x
    else {2..y} |> Seq.fold (fun z _-> z*x) x


http://giovedi.net/img/fsharp5.png


うまくいった。
が、x=0 のときに動かないし、それよりなにより激しくかっこわるい。


F# には実はちゃんと LanguagePrimitives.GenericOne という「汎用の1」がある。

let inline (^) x y  =
    if y = 0 then LanguagePrimitives.GenericOne
    elif y = 1 then x
    else {2..y} |> Seq.fold (fun z _-> z*x) x


http://giovedi.net/img/fsharp6.png


「汎用の0」は LanguagePrimitives.GenericZero 、「汎用の2」とかは 1 から作ればいい。


推論された型情報にある 'member get_One' が LanguagePrimitives.GenericOne によって呼ばれて、型にあった 1 を返しているわけだ。
例えば Seq.sum もシークエンスの要素に member get_Zero を要求していることがマウスオーバーすればわかる。


これでほぼ解決だが、「 LanguagePrimitives.GenericOne って長い」ということだけが悩ましいところ。
が、F# はそれも解決できる。


int64 のリテラルは 123L 、bigint のリテラルは 123I などと、L や I などの接尾辞を付けて区別するわけだが、The F# 2.0 Language Specification の 6.3 Data Expressions を見ると、リテラル接尾辞はユーザ定義できることが書かれている。


こちらの質問サイトのお答え も参考にして次のようなコードを書いてやる。

module NumericLiteralG = begin
  let inline FromZero() = LanguagePrimitives.GenericZero
  let inline FromOne() = LanguagePrimitives.GenericOne
  let inline FromInt32 n = Seq.sumBy (fun _->FromOne ()) {1..n}
end


これで、文脈によって適切に型推論してくれる「汎用リテラル」として 0G や 1G や 2G のように書くことができるようになる。

let inline factorial n =
    if n <= 0G then 1G  // リテラルを 0G, 1G に
    else Seq.reduce (*) {1G..n}

let x  = factorial 5    // int
let xL = factorial 5L   // int64
let xI = factorial 5I   // bigint


http://giovedi.net/img/fsharp7.png


かっこいい？
0G, 1G はパフォーマンスにも全く悪影響はないが、2G 以降は実装からも明らかに遅くなるのでご利用は計画的に。

*1:しかし、max の例では inline を指定しなくてもうまくいく理由はまだよくわかってない。要求されるのが comparison と member の違いだとは思うが。