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

反省はしても後悔はしない

Vim とか備忘録とか。それと関数型言語勉強中

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

F#

背景

先週のなごやか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 がいるの?とか