改めて FizzBuzz 問題

充分に近くで観察したとき、あらゆる問題は奇妙かつ理解しづらいものに見える。

ここまでで見たように、FizzBuzz 問題は、普通に想像するよりもずっとプログラミングの課題として興味深いものです。外側からは単純すぎる問題に見えますが、解の可能性は豊富に広がっています。

すでに述べた解 (最初の解答および修正版) にはよい点も多数ありましたが、ここまで暗黙の内に無視してきた共通の欠点が存在します。巨大な数、例えば 1,000,000 以上に対して FizzBuzz の値を求める際には効率的に動作しないのです。元の解では答えを得るまでに 1,000,000 個の数をたどる必要があります。

この問題を解決するため、以下ではより 関数型の考え方 の特徴を捉えた方法で FizzBuzz 問題の再構築を行います。

関数型プログラミングの根底にある問い
型によるモデリング
合成の活用
型に従って考える

一段上の関数型プログラミングの威力を手に入れましょう。

関数型プログラミングの根底にある問い

関数型の考え方でプログラミング課題を解くときには、次の根本的な問いを考える必要があります。

関数型プログラミングの根底にある問い

この機能は何から何への関数なのか？

FizzBuzz は整数の列から文字列の列への関数です。

写像としての FizzBuzz

fizzbuzz :: [Int] -> [String]
fizzbuzz = map transform [1..100]

さて、ここでまた同じ疑問が生じます。transform は何から何への関数なのか？

もともとのゲームのルールに鑑みれば、この関数は整数 1 を文字列の "1" に、3 を "fizz" に、5 を "buzz" に、そして 15 を "fizzbuzz" に、といった変換を行います。

変換の型

transform :: Int -> String

これで、transform を実装する上で考えなければならない問題は、残り 2 つです。

ゲームのルール
ルールに対する toString の動作

型によるモデリング

ゲームのルールについて考えるところから始めましょう。

ここで我々が考えなければならないルールは以下の 3 つです。

n が 3 で割り切れるならば、結果として "fizz" を加える
n が 5 で割り切れるならば、結果として "buzz" を加える
他のルールが適用できなければ、結果として単に show n とする

言い換えれば、ルールは関数です。ではここで例の質問をもう一度繰り返しましょう。何から何への関数でしょうか？

まず操作するための数が必要です。これを n と呼びましょう。またすでに適用したルールの結果 (文字列のリストになる) も必要です。そして返すのは新しいルールのリストです。

ルールを表す関数の型

type Rule = Int -> [String] -> [String]

fizz ルールをモデリングする第一歩として、以下のような方法が思いつくかもしれません。

最初に思いつく fizz ルール

fizzRule n old = if n `rem` 3 > 0
                 then old
                 else old ++ ["fizz"]

確かにその通りなのですが、しかし同じことを "buzz" に対しても繰り返す必要があります。そこで割る数 (3 か 5) と結果となる単語 ("fizz" か "buzz") をパラメータにすることで重複を除いておきます。

パラメータ化された FizzBuzz ルール

divBy:: Int -> String -> Rule
divBy divisor word n old = if n `rem` divisor > 0
                           then old
                           else old ++ [word]

fizzRule:: Rule
fizzRule = divBy 3 "fizz"

buzzRule :: Rule
buzzRule = divBy 5 "buzz"

消えたパラメータ？

上のコードでは、引数のパラメータである n と old が fizzRole と buzzRule では消えてしまっているかのように見えます。ここではむしろコードをいい感じにするためにあえて省略 (ポイントフリー) しました。

さて、我々のアプローチに対する最初のリトマス試験紙として、次の問題を考えます。他のルールが適用できないときに、数字を返す numberRule をつくりだすことができるでしょうか？

これは難しくありません。必要なのは型に従って考えることだけです。

ルールは数と今までの結果のリストから新しい結果のリストを与える関数だったので、このような関数を考えることができます。

場合分けによる「数字用」のルール

numberRule :: Rule
numberRule n []     = [show n]
numberRule _ result = result

ルールの合成

上で挙げたルールは独立にはうまく動きますが、しかし FizzBuzz ではルールを組み合わせる必要があります。ここが関数型のアプローチが輝く部分です。ルールは関数であり、そして関数の合成 (関数合成の記法) は極めてシンプルです。

fizzRule に対する関数呼び出しの結果は buzzRule の引数として渡すことができ、さらにその結果も numberRule に引き渡すことができます。numberRule n (buzzRule n (fizzRule n [])) のような入れ子になった呼び出しでも機能としては問題ありませんが、関数合成演算子 (.) を使ったほうが見た目が綺麗です。

関数で表されたルールを組み合わせる

rules :: Rule
rules n = numberRule n . buzzRule n . fizzRule n

Note	この方法のいいところふたつのルールを組み合わせた結果として何が得られるでしょう？そう、結果もまたルールになるのです！

型に従って考える

すべてのルールの合成について理解できたところで、toString の機能について考えることができます。すべてのルールを数字に適用した結果、最後に適用するための関数です。

再度、例の根本的な問いを繰り返しましょう。toString は何から何への関数なのか？

ルールを受け取り、その結果を文字列として表示する
ルールが適用されるべき数を受け取る
文字列を返す

toString の型

toString :: Rule -> Int -> String

実装はほぼそのまま書き下すだけです。結果の文字列からなるリストを作るためには、ルールを数と初期値が空のリストに適用する以外に選択肢はありません。

結果として得られた文字列のリストを連結することで、ひとつの文字列にまとめます。すでに関数が存在しそうな感じですね。型は [String] → String となる必要があります。このような関数を Froogle で検索してみると、joined が見つかります。この関数は区切り文字として使用する文字列をもう一つ引数に取りますが、ここでは区切り文字は必要ないので空の文字列を与えましょう。

ルールを適用して単独の文字列を得る

toString :: Rule -> Int -> String
toString rule n = joined "" (rule n [])

ここで見た toString は任意のルールに対して有効です。ルールを合成したものすなわち rules は自分自身もルールになるため、全体として transform を適用することができます。

全体をひとつに

すべてのルールを合成したものと toString が使えるようになったため、ついに出発点だった transform を実装することができるようになりました。覚えていると思いますが、この関数の型は Int → String です。

シンプルな変換

transform :: Int -> String
transform n = toString rules n

最終的な解は次のようになります。ここでは型宣言は省略していますが、そもそも型宣言は付加的な情報であり、なしでも完全な型安全性に保っていることに注意しましょう。

完全な解答

type Rule = Int -> [String] -> [String]

divBy divisor word n old = if n `rem` divisor > 0
                           then old
                           else old ++ [word]

fizzRule = divBy 3 "fizz"
buzzRule = divBy 5 "buzz"

numberRule n []     = [show n]
numberRule _ result = result

rules n = numberRule n . buzzRule n . fizzRule n

toString rule n = joined "" (rule n [])

transform n = toString rules n

main _ = for (map transform [1..100]) println

まとめ

今回得られた新しい解は次のような性質を持ちます。

これまでの解のいいところはそのまま
巨大な数をパフォーマンス上問題なく扱える
より簡単に新しいルールを定義して既存のルールと組み合わせることが可能 (いわば組み込みドメイン特化言語)
ルールが関数として定義できるので、非常に広くいろいろな形で使用できる

関数や、関数としての型がいかに素晴らしいものか (改めて) 確認できたことと思います。

何から何への関数なのか？

「この関数は何から何への関数なのか」という関数型プログラミングの根本的な問いを考えることで、使用する言語が何であれ、プログラミングの方法が変わることでしょう。

Note	謝辞多くの刺激的な議論と示唆を提供してくれたダニエル・クレーニに多大なる感謝を。

参考文献

Froogle	Lookup `joined` by type: http://hoogle.haskell.org:8081/?hoogle=%5BString%5D%20-%3E%20String
Kevlin Henney	gives a similar example in terse JavaScript in this video: https://www.youtube.com/watch?v=FyCYva9DhsI around minute 21ff, calling it "too clever"
Maciej Pirog	FizzBuzz in Haskell by Embedding a Domain-Specific Language https://themonadreader.files.wordpress.com/2014/04/fizzbuzz.pdf

改めて FizzBuzz 問題