Linuxを日常的に使う実験ブログ

FizzBuzz問題で考えるHaskellと問題解決のアプローチ

 2021-07-31

 プログラミング

こんにちは。今回のテーマは「FizzBuzz問題で考えるHaskellと問題解決のアプローチ」です。Haskellのノウハウ記事でもなければ学習記事でもないです。本来チラシの裏に書くべきポエムです。コーヒーブレイクにどうぞ。(ならないかも知れませんが・・・) ※HaskellでFizzBuzz問題に挑戦しました!という記事ではないです。あしからず。 [adsense02] 【目次】 プログラミング言語とパラダイム Haskellとは FizzBuzz問題とは FizzBuzz問題へのアプローチを考える まずPythonで表現してみる Haskellで表現してみる

プログラミング言語とパラダイム

プログラミングを行う際には解くべき問題をどのようなアプローチで解くかを考え、そのアプローチをコードで表現します。アプローチとは手段や発想と読み替えても良いと思います。当然、関数型プログラミングにはその関数型パラダイムに適したアプローチがあるわけです。一般的に関数型プログラミングをするときにはデータがどのような状態にあるべきか?について記述します。map, filter, fold(reduce)をなどのツールを駆使しデータ構造に関数を作用させ解に導く手法もその1つです。一方で求め方の手続きを記述する命令型プログラミングでは副作用のある代入処理やループを多用し計算過程を指示するアプローチがとられます。今回は敢えて関数型パラダイムと命令型パラダイムの両方のアプローチでHaskellでFizzBuzz問題を考えてみることにします。

Haskellとは

Haskellは副作用のない純粋な関数型言語です。関数型言語とは定義が曖昧な言葉ですが、ここでは欲しい結果の「求め方の手続き」を記述するのではなく、値の関係性や状態を関数および式で表現することで解を得る関数型プログラミングのパラダイムに対応した言語という意味合いで使っています。その意味で「求め方の手続き」を記述する命令形パラダイムに慣れた方からは馴染みづらい言語と思われることも多いようです。

FizzBuzz問題とは

説明するまでもないFizzBuzz問題ですが、簡単に説明すると1,2,3…という順にnまで整数を挙げていって3で割り切れる時はFizz、5で割り切れる時はBuzz、3でも5でも割り切れる時はFizzBuzzと言うゲームが元になっているプログラミングの問題です。プログラミングでは実際に発言する代わりに標準出力で対応します。

FizzBuzz問題へのアプローチを考える

この問題は1からnまでの整数を順に処理し、条件により出力を変えるというものですが、今回は3つのアプローチを考えました。※今回は単純化のためn=30とします。

  • アプローチ1: 1からnまでの整数の配列に変換用の関数を作用させ出力用配列を得る。その配列の内容を出力する
  • アプローチ2: 1からnまでカウントアップさせて、その数値に対応する結果を出力する処理を繰り返す
  • アプローチ3: 1からnまで順に調べながら出力用の配列を結合する処理を繰り返し配列を得る。その配列の内容を出力する

アプローチ1は関数型パラダイムでよく用いられる手法で、数値配列を出力文字列に関数を考えていきます。アプローチ2は典型的な命令型パラダイムの発想で、for文やwhile文などとして知られるループ処理です。アプローチ3も命令型パラダイムの発想ですね。forループの中で配列を結合していくようなイメージです。尚、Haskellは関数型言語だからアプローチ1で解こうねってお話ではありません。

まずPythonで表現してみる

アプローチ1に関してはPythonだとこんな感じです。関数型パラダイムに慣れた人が真っ先に思いつく手法かなと思います。データのリストを作りそのリストに変換を加える関数を適用して解を導出する手法です。 アプローチ1のPythonプログラム

# FizzBuzz変換用の関数
def conv(i):
    if i % 15 == 0:
        return 'FizzBuzz'
    elif i % 3 == 0:
        return 'Fizz'
    elif i % 5 == 0:
        return 'Buzz'
    else:
        return str(i)
# 出力
list(map(print, map(conv, range(1,30))))

アプローチ2に関してはPythonで書くとこんな感じです。手続き型言語に馴染んでいる人にはおなじみのループですね。ループの中でカウントアップと出力を行っています。下のPythonの例でのcnt変数は破壊的な再代入が行われており、ループが繰り返されるたびに1,2,3..と値が増えていきます。 アプローチ2のPythonプログラム

cnt = 1
while cnt <= 30:
    if cnt % 15 == 0:
        print('FizzBuzz')
    elif cnt % 3 == 0:
        print('Fizz')
    elif cnt % 5 == 0:
        print('Buzz')
    else:
        print(str(cnt))
    cnt += 1

アプローチ3はアプローチ1とアプローチ2の合わせ技みたいな感じです。結果としてはアプローチ2のように文字列配列を得るのですが、その方法としてforループ内部で文字列の配列を結合しています。下のPythonの例ではforループの中で配列に対して破壊的な操作を行っています。Pythonで表現してみると以下のプログラムのようなイメージです。 アプローチ3のPythonプログラム

li = []
for i in range(1,31):
    if i % 15 == 0:
        li.append('FizzBuzz')
    elif i % 3 == 0:
        li.append('Fizz')
    elif 1 % 5 == 0:
        li.append('Buzz')
    else:
        li.append(str(i))

list(map(print, li))

Haskellで表現してみる

で、ここからが本題ですね。上記のアプローチをHaskellで表現するとしたらどうなるか?を考えてみましょう。関数型パラダイムでプログラミングをする際にはアプローチ1のようにmapを使ってリストを別のリストに変換する手法が多いように感じます。アプローチ2,3に関してはそもそも解法として選択しないこケースが多いでしょう。しかし今回は敢えて破壊的な代入が必要と思われるアプローチをしてみます。

アプローチ1: mapによるリストの変換

まずHaskellでアプローチ1の方法で解く場合を考えます。これは目新しいことは何もなく、map(あるいは(<$>), liftM)を用いてリストの変換を行えば良いだけです。

main :: IO ()
main = mapM_ putStrLn mkList

mkList :: [String]
mkList = map convert list
  where
    list = [1..30] :: [Int]
    convert :: Int -> String
    convert n
      | n `mod` 15 == 0 = "FizzBuzz"
      | n `mod` 3 == 0 = "Fizz"
      | n `mod` 5 == 0 = "Buzz"
      | otherwise = show n

簡単ですね。1から30までの整数のリストに対してmap関数でfizzBuzz関数を適用して文字列リストを作成し、この文字列リストをIOアクションであるputStrLnに対してmapM_で繰り返し出力するようにしています。このようにリストデータを操作することでfor文による繰り返しができなくとも問題を解くことができることがわかりました。では副作用を許さない純粋関数型言語のHaskellでforループの中でガシガシ値が変更されるアプローチ2やアプローチ3の発想をHaskellで表現できるか見ていきましょう。

アプローチ2: Haskellでカウントアップ

アプローチ2のようにループの中で変数がカウントアップしていくような処理はHaskellで書けないのか?Haskellでは破壊的な再代入は許されないので、このような処理はできないと誤解している方もいるようですが、状態系のモナドによって手続き型プログラムのような思考のプログラムを書くことは可能です。(意味があるかはまた別の話ですが) 処理を繰り返す度に値がカウントアップされ、その値を出力する繰り返し処理をHaskellで表現してみましょう。 アプローチ2のHaskellプログラム

import Control.Monad.IO.Class (liftIO)
import Control.Monad.Trans.State

main :: IO ()
main = do
  evalStateT loop 1 -- cntの初期値を1とする

loop :: StateT Int IO ()
loop = do
  cnt <- get -- 現在のカウンター値を取得
  if (cnt <= 30)
    then do
      -- 出力処理
      liftIO $ putStrLn $ convert cnt
      -- cnt値をカウントアップ
      put (cnt + 1)
      -- 再帰呼び出し
      loop
    else return ()

    where
      convert :: Int -> String
      convert n
        | n `mod` 15 == 0 = "FizzBuzz"
        | n `mod` 3 == 0 = "Fizz"
        | n `mod` 5 == 0 = "Buzz"
        | otherwise = show n

どうでしょうか?ものすごく「解の求め方の手順」を書く命令型プログラミングに見えますよね。おそらくこのコードはHaskellの文法が分からない方でも何となくニュアンスが分かると思います。因みにStateTモナド変換子を使わず同様のことをやろうと思うと以下のようになるかと思います。再帰呼び出し時にカウントアップして引数に渡しています。 アプローチ2のHaskellプログラム(2)

main :: IO ()
main = loop 1
  where
    loop :: Int -> IO ()
    loop cnt | cnt <= 30 && n > 0 = do
             -- 出力処理
             putStrLn $ convert cnt
             -- カウントアップして再帰呼出し
             loop (cnt + 1)
           | otherwise = return ()

    convert :: Int -> String
    convert n
      | n `mod` 15 == 0 = "FizzBuzz"
      | n `mod` 3 == 0 = "Fizz"
      | n `mod` 5 == 0 = "Buzz"
      | otherwise = show n

アプローチ3: ループ内でリストへ追加処理を行う

ここまでアプローチ1ではmapで変換関数を適応させ文字列リストに変更しました。また、アプローチ2ではStateTモナド変換子を用いて繰り返しのたびにカウントアップし、出力(IOアクション)するループ処理を見てきました。ではアプローチ3はどうでしょうか?アプローチ3は「与えられた値を1つずつ調べて処理する」ことで最終的に欲しい文字列配列を得ようとします。これは行列やベクトル全体を変換する関数を適用するアプローチ1とは大きく異なる発想です。Haskellで「1つずつ調べて結果を積み上げていく」場合に使う道具にfoldl/foldrがあります。foldlは左側から適用、foldrは右側から適用します。今回はfoldlを使います。 コードを先に示すと アプローチ3のHaskellプログラム例

main :: IO ()
main = do
    mapM_ putStrLn $ foldl fizzBuzz [] [1..30]
    where
        fizzBuzz :: [String] -> Int -> [String]
        fizzBuzz l i
            | mod i 15 == 0 = l ++ ["FIZZBUZZ"]
            | mod i 3 == 0 = l ++ ["FIZZ"]
            | mod i 5 == 0 = l ++ ["BUZZ"]
            | otherwise = l ++ [(show i)]

というコードになります。一見、mapを使った場合と変わらないように見えます。が、何か気付かないでしょうか?そうです。これは正にアプローチ3の発想です。mapを使ったアプローチ1の場合は整数リストを文字列リストにInt -> Stringという関数を適用して変換したのに対して、foldlを用いた場合は整数リストを頭から「1つずつ処理」して「変換した文字列をリスト末尾に追加」するという処理を行っているのです。これは命令型パラダイム的な発想を表現しています。(飽くまで発想です)もちろん実際のHaskellの処理で破壊的なリストの追加処理が起きているわけではありません。更にはアプローチ3のPythonコードと同義でもありません。しかし「数値を1つずつ調べて変換して文字列リストにどんどん追加しよう!」という発想でプログラミングできました。 同様の発想でState sモナドで実装すると以下のようになります。 アプローチ3のHaskellプログラム例(2)

import Control.Monad.Trans.State
import Control.Monad (forM_)

main :: IO ()
main = do
    mapM_ putStrLn $ execState loop []
    -- execStateで初期値を[]としてloopを実行
    -- 得られた文字列リストを表示
    where
    -- 変換とリスト結合のループ処理
    loop :: State [String] ()
    loop = do
        forM_ [1..30] mkList
        -- State sモナドアクション
        -- mkList 1
        -- mkList 2
        -- ...
        -- mkList 30
        -- が実行される
        return ()
        
    -- 数値を文字列に変換してListを結合
    mkList :: Int -> State [String] ()
    mkList i = do
        m <- get
        put (m ++ (convert i)) -- リスト結合処理
        return ()

    -- 数値をfizzBuzzに変換
    convert :: Int -> [String]
    convert i
        | mod i 15 == 0 = ["FizzBuzz"]
        | mod i 3 == 0 = ["Fizz"]
        | mod i 5 == 0 = ["Buzz"]
        | otherwise = [(show i)]

こちらの方がfoldl関数を用いた場合よりもより直接的に配列を追加して結合しているイメージがつきやすいでしょうか?モナドアクションでforループっぽいことをやっている感じを出すために敢えてmapM_ではなくforM_関数を使ってみました。1つ1つの値を調べながら変換した文字列を配列に追加していくというアプローチをコードに落とし込むとこのように表現できます。

何が言いたかったのか

で、結局なんなのか?と思ってる方、ごめんなさい。大した主張もないのですが、「関数型プログラミング」とか「関数型言語」なる言葉にあまりとらわれなくて良いんじゃないか?ということでこんな文章を書いてみました。 Haskellは関数型言語なんだから今までの発想は捨ててモノの見方を変えないと!と頑張ってる方に「もっと肩の力を抜きましょう」というエールを送りたいと書きました。 Haskellについての解説はとても賢く優秀な方が書かれていて抽象化された概念やモナドの理解などが前面に出ているため、手垢にまみれた「日常のちょっとしたこと」を解決するツールとしての面があまり表に出ていないように感じています。「関数型言語の代表」とか「数学的に美しく短く書ける言語」などと喧伝されるあまり、ゴリゴリ手続き型の発想で書いていると後ろめたい気持ちになり「より関数言語的な発想で」とか「より美しく」「より抽象的なモデル化を」みたいな強迫観念に駆られ、結果的にハードルが高い言語になっている気がします。美しさやスマートさは大切ですが、時に泥臭くても問題を解決する手段が必要な場合もあると思います。 そこでFizzBuzz問題を用いて、一見すると命令型パラダイムっぽい考え方で副作用を起こさないと書けないだろうと考えられるアプローチであっても「なんとかなるよ」ということが伝わる記事を書いてみたいと思いました。「Haskellで書くんだから発想を変えないといけない」と縛られずいろんな解法で対応できることを知っていれば少し気が楽になるものです。もちろん最初からキレイにスマートに書けるならそれに越したことはないです。でも、最初から美しい解法を目指して挫折するぐらいなら泥臭いアプローチでもHaskellを使ってみる勇気とキッカケを与えられれば良いなと思い記事を書きました。

最後に

長い記事にお付き合いいただきありがとうございました。まとまらない内容で申し訳なかったです。楽しくHaskellを書きましょう。 【関連記事】 タイル型ウィンドウマネージャXmonadを使う(基礎編) 【2019年版】プログラミングが捗るコーディングに適したフォント集 [adsense]