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

Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

計算機コンピュータにおけるFizzとBuzz(PyCon2013復(習|讐)編)

 PyConでFizzBuzzについて話をしてきました。いろいろ考えた結果、強引な英語でやるということをやりました。笑ってくれた人が半分くらいいて、真面目に聴きたい人はいらいらした感じになったのは申し訳ないです。ちなみに、スライドはしたのところにあります。

Fizz and buzz of computer programs in python.

 ※ブックマークでのご指摘通り、19ページの部分でelifが抜けていたので、意図通り動かないことがわかりました。ありがとうございます。

 で、今回のブログ記事に関しては、本当は話したかったけど話せなかったことについて補足説明をしたいと思います。

FizzBuzzという題材について

 そもそも、なぜFizzBuzzという題材を選んだのか、については以下の通り。

  • FizzBuzzには「反復」と「分岐」という二つのポイントがある
  • 「反復」と「分岐」と一口にいっても、色々な実装方法がある

 ということです。基本的に「反復」といえば、いわゆる上から順番に実行されていくプログラムであるならば、for文などの実装が考えられます。これは一番簡単な方法です。

反復について

 しかし、「反復」自体は、プログラミングに詳しい人であるならば、「再帰」と、「高階関数」による再現がありえます。「再帰」に関しては、もっと具体的にいうならば、「自分自身を、手続きとして呼び出す関数」といえばいいのでしょうか。また、「高階関数」に関しては、各配列に対して関数を適応する形というのが考えられます。これら二つの実現方法については、Pythonでは下のような形が考えられるでしょう。

高階関数について

 まず、高階関数から考えてみます。

 Pythonにはmap関数があります。これは第一引数に関数を取る関数であり、その関数を各要素に適応します。実は、これ自体はPythonで使われるrangeと構造的には一緒、という考え方もできます。

 というのは、Pythonのforは、配列から要素を一つずつ取ってくる形になっていて、さらにいうと何らかのオブジェクトが__iter__属性をもち、nextを持っているならば、基本的にIteratorと見なしてforで使えたりします。

for i in range(10):
    print(i)
[print(i) for i in range(10)]
list(map(print, range(10)))

 

 基本的には、mapというのは、なんらかの適応後の結果を配列にパックしなおすので、関数の適応結果が欲しければmapを使い、普段はforを使うほうがいいかもしれません。

 また、Python3系からmapは遅延評価(配列をすぐに生成しない、評価されたときに始めて使う)になっているので、もしすぐにListオブジェクトが必要になるならば、リスト内包記法を使うほうがいいのかもしれません。

 このように、見た目的にはどれも同じような挙動をしますが、このあとに何をしたいのか、によって、使用するべきものは変化します。

再帰関数について

def loop(limit, start=1):
    u"""
  :param limit: 到達したら終了する閾値 
  :param start: カウントとして開始が行われる場所, デフォルトでは1
  """
    (start > limit) or loop(limit, start=start + 1)

 ちょっとプレゼン資料とは異なりますが、安全のために少しだけ変更を加えています。

 普通、再帰といえば、基本的には閾値以内での関数呼び出しであり、そして閾値での「関数を呼び出さない分岐」で設計されるものだと理解しています。素直に書くと下のようになるかと思われます。

def loop(limit, start=1):
    if start is not limit:
        return loop(limit, start + 1)
    return start

 もちろん、再帰自体には入れ子状にスタックを作っていく再帰と、入れ子状にしない末尾再帰があります。

 末尾再帰にしないほうに関しては、基本的にシンプルな作りになるし、また木構造を表現するときに素直に書ける、というのが魅力的なポイントである一方で、例えばPythonの場合だとスタック領域に制限がかかっているので、そのたびになんとか「再帰」を浅くする工夫が求められます。

結果を違うものにする(結果の出力)

 さて、普通は結果を違うものを取り出す場合、ifという条件式を使う場合が多いかと想われるのですが、ifだけではなく、他の方法も考えられます。

Listの使用

 まず一つに、Listの使用が挙げられます。

 例えば、何らかの数字を3で割った時の余りのパターンを考えてみましょう。通常、3で割った場合、0, 1, 2が余りの可能性として出てきます。今回の場合、Fizzを表示させたい場合は、3が割り切れる数です。ということは、あまりが0になる場合だと考えることができます。従って、ListからFizzであるか、そうではないかという場合は、下のような実装が考えられるでしょう。

fizz = lambda x: ["Fizz", "", ""][x % 3]
for x in range(100):
    print fizz(x)

 しかし、これは冗長です。というのは、本当なら「割り切れるなら"Fizz"、割り切れないなら何もない文字」と分けたい筈だからです。一応、Python的には、Trueはキャストされるときに1、Falseはキャストされるときに0になりますので、例えばboolという関数で無理にTrue or False、もっといえば0と1に収縮させることが出来ます。

fizz = lambda x: ["Fizz", ""][bool(x % 3)]

 Buzzも同じことが出来ます。

buzz = lambda x: ["Buzz", ""][bool(x % 5)]

 さて、ここまで書いてみて、このままだと数字を表示する部分がありません。実は、Pythonは「""(=空の文字列)」はFalseとして判定されます。もし、Fizz or Buzz or FizzBuzz、どれかに当てはまる場合は文字列が入っているはずです。そして、何らかの文字列が入っている場合には、BoolをキャストするとTrueになります。このことを利用してみましょう。

fizzbuzz = lambda x: [x, fizz(x) + buzz(x)][bool(fizz(x) + buzz(x))]

 これでも冗長ではあるのですが、(というのも、fizz(x) + buzz(x)が二度使われている)言わんとしたいことはわかるかと期待しています。

or の利用

 近代的なプログラムだったりすると、例えばandやorがつながっている場合、何処かがTrueやFalseになっていると、以降の連結された値の評価をしないという戦略を取ったりします。これを逆手に取ることが出来ます。例えば次のような分岐を作ることが可能です。

fizzbuzz = lambda x: (fizz(x) + buzz(x)) or x

 そして、Pythonだと、orなら最後にTrueになったもの、あるいはandなら最後にFalseになったものの値が返ってきます。

蛇足: or の利用の構造について

 もうちょっと見てみましょう。実際のところ、fizzであるのか、あるいはbuzzであるのかということ自体、実は2進法で表現できるということがあります。

 例えば、次のような配列を考えてみましょう。

[bool(fizz(x)), bool(buzz(x))]

 このパターンで、可能性のある組み合わせは下の通りです。

[0, 0]
[1, 0]
[0, 1]
[1, 1]

 これはまさに2進法と捉えることが可能です。つまり

[0, 0] # => 0
[0, 1] # => 1
[1, 0] # => 2
[1, 1] # => 3

 という感じです。とすると、Listの構造を利用して、下のようなことも可能になるわけです。

fizzbuzz = lambda x: [x, "Fizz", "Buzz", "FizzBuzz"][(not x % 5) * 2 + (not x % 3)]

最後に

 さて、さまざまなFizzBuzzの実装について見てきました。FizzBuzzはとてもシンプルな問題です。しかし、そのシンプルさというのは、逆に言えば、工夫がしやすい問題でもあるということです。例えば、上の二進法を利用した場合、PHPの仕様である「文字列がfunctionになる(!)」というのを利用して、下のようなコードが書けます。

<?php
    function _00($i) { echo $i; }
    function _10($i) { echo "Fizz"; }
    function _01($i) { echo "Buzz"; }
    function _11($i) {
        echo _10($i);
        echo _01($i);
    }

for ($i = 1; $i < 101; $i++) {
    
    $fizz = $i % 3 === 0; $fizz = (int) $fizz;
    $fizz = (string) $fizz;
    
    $buzz = $i % 5 === 0; $buzz = (int) $buzz;
    $buzz = (string) $buzz;
    
    $fizzbuzz =  "_" . $fizz . $buzz;
    $fizzbuzz($i);
    echo "\n";
}

 また、FizzBuzzのProcess自体を一つの「副作用」として捉えて、HaskellのMaybeモナドを利用して、下のようなコードも書けます。

type IsFizzBuzz = Maybe String 

is_n:: Integer -> Integer -> Integer
is_n x y = x `mod` y 

fizz :: Integer -> Integer
fizz x = is_n x 3

buzz :: Integer -> Integer
buzz x = is_n x 5

maybe_div :: Integer -> String -> IsFizzBuzz -> IsFizzBuzz
maybe_div 0 str m = case m of
    Nothing -> Just str
    Just x  -> Just $ str ++ x
maybe_div _ str m = m

maybe_fizz :: Integer -> IsFizzBuzz -> IsFizzBuzz
maybe_fizz x m = maybe_div is_fizz "Fizz" m
    where is_fizz = fizz x 

maybe_buzz :: Integer -> IsFizzBuzz -> IsFizzBuzz
maybe_buzz x m = maybe_div is_buzz "Buzz" m
    where is_buzz = buzz x

maybe_fizzbuzz :: Integer -> IsFizzBuzz -> String
maybe_fizzbuzz x m = case m of
    Nothing -> show x
    Just x -> x

maybe_process :: Integer -> String
maybe_process x = maybe_fizzbuzz x $ is_fizzbuzz x
    where is_fizzbuzz x = maybe_fizz x $ maybe_buzz x Nothing

main :: IO ()
main = go maybe_process

※:バグがあったので一部修正

 そんなわけで、FizzBuzzの問題について、深く考えることで、「反復」と「分岐」とは何かについて、より知れるのかもしれません。

ちなみに

 いろんな方法でFizzBuzzをやろうという主旨のレポジトリもあったりします。 self-study-ja/FizzBuzzStyleGuide · GitHub