読者です 読者をやめる 読者になる 読者になる

Excel-DNA で XLL をつくる (その17) を F# でやってみた

F# Excel

今自分の中で Excel-DNA がとてもアツいです。
で、Excel-DNA のことを非常にわかりやすくまとめている supermab さんという方がいるのですが、今日はその方のエントリを F# でやってみた、という話です。
Excel-DNA については supermab さんのブログの Excel-DNA タグ をどうぞ。

ところで、F# のような関数型言語は、並列化処理に向いているようですが今回のような組合せ探索の問題はどのように記述出来るのでしょう?Excel-DNA と F# の組合せは、とても興味のあるところです♪

Excel-DNA で XLL をつくる(その17)

あれ?なんか呼ばれてる?ということでやってみました。
ただし並列処理は今回やってないです。お手軽にやるなら Array.Parallel モジュールの関数群を使う感じでしょうか。
今回は、より簡潔に書けるよー、という部分を強調した感じに書いてみました*1


完成品は github に上げてあります。
https://github.com/bleis-tift/DNA/tree/supermab17


コメント入れても 30 行以下、コメント抜くと 20 行以下です。短い!
元の C# での実装に比べると、解を二次元配列として返すメソッドが無いですが、それを実装したとしても数行です*2

module Combination

let combIf cond xss =
  // 補助用関数
  //   要素があるときは、先頭要素をばらして再帰呼び出し
  //   要素が無いときは、
  //     計算データ(tmp)が条件を満たせば反転してリストに包む
  //     満たさなければ空のリストを返す
  let rec combIf' cond tmp = function
  | xs::xss -> xs |> List.collect (fun x -> combIf' cond (x::tmp) xss)
  | [] when cond tmp -> [tmp |> List.rev]
  | [] -> []
  
  // 組み合わせ探索
  xss |> combIf' cond []

open ExcelDna.Integration // あ、これ結局使ってない

let AnsCount(range: obj[,], trg: int) =
  // 二次元配列をint list listに変換
  let range =
    [0..range.GetLength(1) - 1]
    |> List.map (fun i -> [ for x in range.[*, i..i] -> x :?> float |> int ])

  // 組み合わせ探索
  range |> combIf (List.sum >> ((=)trg))
        |> List.length

二次元配列をリストのリストに変換している部分ですが、このあたり F# は短くかけてとてもいい感じです。
ちなみに、range.GetLength の引数を 0 にして、range のインデクサの * と i..i を逆にすると、行と列が入れ替わったリストになります。


型も、AnsCount の引数と、obj のキャスト部分の計 4 回しか書いていません*3
これだけで、他のすべての部分は型推論によって適切な型が付けられます。動的型付けじゃないですよ。


combIf の呼び出し部分では、関数を合成しています。関数の合成が手軽に書けるのは、関数型言語である F# ならではです。
C#VB だと、こうはいきません。


補助関数である combIf' は、関数内関数となっています。
combIf' を使うのは combIf だけなので、combIf 以外からはアクセスできないように関数内関数として定義しています。
識別子名として、「'」を含むことができていることにも注目してください。
これは途中に含まれてもいいため、「it's」なども識別子として使えます。


combIf' で使っているパターンマッチも強力です。
switch 文を強力にしたもの、と説明されがちなパターンマッチですが、xs::xss のようにデータ構造を分解し、変数に格納するといったことも簡単に行えます。
インデックスによるランダムアクセスは使用していませんので、インデックスを 1 間違えるといったよくあるエラー *4 は起こりえません。
行のインデックスが・・・とか、列のインデックスが・・・とか考えなくていいので、とても楽ができます。


パターンマッチは網羅性のチェックもしてくれるのですが、今回は when を使ったので、条件を満たさない空のリストの場合の考慮を忘れてしまい、テストで検知しました・・・
ここを

let rec comb tmp = function
| xs::xss -> xs |> List.collect (fun x -> comb (x::tmp) xss)
| [] -> [tmp |> List.rev]

として、呼び出し側でフィルタする形にすればよかったのですが、色んな機能が使いたかったのでこれで。
ちゃんとしたプログラムを書くときは、できる限り when は使わず、網羅性のチェックが働くようなコードを心がけましょう。


全体を見てみましょう。一度変数に代入した値を書き換えていないことがわかるでしょうか?
このように、一度代入した変数を書き換えないので、変数の値に気を配る必要がなくなり、より脳力を消費せずにプログラミングすることができます。


どうでしょうか?
F# の魅力が伝わったならうれしいです。

*1:あといろんな機能を使ってみました

*2:'a list list を 'a[,] に変換する関数を書くだけなので、F# の練習としてやってみるのもいいでしょう

*3:trg の型指定も実は省略できるのですが、ドキュメント用として書いておきました。

*4:off-by-one error と呼びます。