今更ながら F# で逆 FizzBuzz を解いてみた。それと List モナド

背景

先週のなごやかScala #9にて、逆 FizzBuzz 問題というものを Scala で解いたものをコードレビューするというのがありました。
はてなダイアリーふっかつと逆FizzBuzz問題をScalaで解こう（前編） - スノトラさんのつれづれ日記
元ネタは多分これ
逆FizzBuzz問題 (Inverse FizzBuzz) - 猫とC#について書くmatarilloの雑記

私はその時は問題を知らなかったのでコードレビューの時は聞き流していたのですが、帰ってから調べてみたら面白そうだったので挑戦してみることにしました。Scala で書くのは sunotra さんにおまかせするとして、私は F# でやってみました。

ひけっていけいさん → List モナド！

元ネタの Scala のコードを読むと [1..1], [1..2], ... , [1..100], [2..2], [2..3], ... というリストのリストから答えとなる文字列にが合致するものを探すアルゴリズムになっています。（正確にはすべての要素を FizzBuzz 化させたものを Map にしていて、入力の文字列のリストをキーとして答えを取り出している）
答えの候補となるものをとりあえず全部並べていく = 非決定計算ということで、コンピュテーション式を使った List モナドで実装してみました。
実はコンピュテーション式よくわかっていないので*1、List モナドのところは以下を参考にしました。
F#で順列(Permutation)と組み合わせ(Combination)。YOU、Listモナドしちゃいなよ。集合モナドもあるよ。 - Bug Catharsis。

書いてみた

let fizzbuzz x =
    match (x%3, x%5) with
    | 0, 0 -> ["FizzBuzz"]
    | 0, _ -> ["Fizz"]
    | _, 0 -> ["Buzz"]
    | _, _ -> []

let tofizzbuzz xs = List.collect fizzbuzz xs

type ListBuilder() =
    member this.Bind (m, f) = m |> List.map f |> List.concat
    member this.Return x = [x]
    member this.Zero () = []

let list = ListBuilder()

let answers input = list {
    let! start = [1..100]
    let! end = [start..100]
    if tofizzbuzz [start..end] = input then
        return [start..end]
}

let inverse_fizzbuzz input =
    match answers input with
    | [] -> []
    | xs -> List.minBy List.length xs

printfn "%A\n" <| inverse_fizzbuzz ["Fizz"; "Buzz"; "Fizz"; "FizzBuzz"; "Fizz"; "Buzz"]
(* [9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20] *)

上のコードの answers のところでコンピュテーション式を使っています。本来なら2重ループになるところがすっきり書けていて素敵ですね。

逃げ

F# 力低いので上のコードは突っ込みどころ満載かも知れません。

*1:なんで Zero がいるの？とか