剰余をつかわない FizzBuzz
twitter で剰余演算をつかわずに FizzBuzz をどう実装するかというのを見かけて、それだったら…とつくってみたくなった。のでつくってみた。
カッとなって twitter に投げたときは zip して uncurry (++) などと回り道をしたけれど、そこは zipWith で置き換えられるので、こんなかんじになる。:
cr = concat.repeat fs = cr ["Fizz", "", ""] bs = cr ["Buzz", "", "", "", ""] fb n = let v = (zipWith (++) fs bs) !! n in if v == "" then show n else v -- そして map fb [1..100]
解説
fs は、 ["Fizz", "", ""] というリストの繰り返し (repeat) [ ["Fizz", "", ""], ["Fizz", "", ""], ["Fizz", "", ""], ...] をつくり、これを (concat して) 平らにして ["Fizz", "", "", "Fizz", "", "", "Fizz", "", ...] をつくっている。
同様に ["Buzz", "", "", "", ""] から bs = ["Buzz", "", "", "", "", "Buzz", "", "", ...] をつくる。
つぎに fs と bs の各要素を順に組み合わせたリストをつくる。
これは zipWith (++) fs bs でできる。 fs と bs それぞれの要素を先頭から順にとって (++) で結合した結果からリストをつくる処理になる。
(もともと zip は zipWith (,) で定義できて、タプルを生成する関数 (,) をふたつのリストに適用している)
さて、できあがったリストは ["FizzBuzz", "", "", "Fizz", "", "Buzz", "", ...]。
この要素が空文字列 "" になるところを数値からつくった文字列 (show n) に置き換えればよい。
まとめると \n -> let v = (zipWith (++) fs bs) !! n in if v == "" then show n else v。
これは FizzBuzz リストの n 番目の要素をとってこれを v とし、この v が空文字なら show n、そうでなければ v の値となる関数。
tweet での uncurry の説明
zipWith (++) fs bs を、 tweet したときは map (uncurry (++)) (zip fs bs) でつくっていた。
この動きだけれど、まず fs と bs を zip してリストをつくる。これはタプルのリスト、 [("Fizz", "Buzz"), ("", ""), ("", ""), ("Fizz", ""), ("", ""), ("", "Buzz"), ...] のようになる。
このリストに (map (uncurry (++))) を適用する。リスト内の各タプルに、関数 uncurry (++) を適用する、ということ。
もともと関数 (++) はリストを受け取って、さらにリストを受け取る関数(そしてこの関数はリストを返す)を返す高階関数。だからタプルには適用できない。ところが uncurry を (++) に適用するとあら不思議、高階関数 (++) がタプルを受け取ってリストを返す関数になってしまう。
(++) :: [a] -> [a] -> [a] uncurry (++) :: ([a], [a]) -> [a]
uncurry の実装はこんなかんじ:
uncurry :: (a -> b -> c) -> (a, b) -> c uncurry f = \(x, y) -> f x y
型は、 a -> (b -> c) という関数を受け取って (a, b) -> c という関数を返す高階関数。実装は関数 f を受け取って、関数 \(x, y) -> f x y という関数を返す。タプルを受け取って、そのタプルの要素をもとの f に渡すだけ。なんというか、こんなにさらっと書き下すだけで関数のインターフェースががらっと変わってしまうのが、ほんと、楽しい。
閑話休題。
結局、タプルのリストに uncurry (++) を適用することで、タプルの前後要素が関数 (++) で連結される、と、そういう動きになる。
別解
Maybe をつかったほうが、より、 Haskell っぽいんじゃないかなって。:
cr = concat.repeat fs' = cr [Just "Fizz", Nothing, Nothing] bs' = cr [Just "Buzz", Nothing, Nothing, Nothing, Nothing] fb n = fromJust $ zipWith mappend fs' bs' !! n `mplus` Just (show n)
でも、ちょっと読みにくい、よね? 残念だなあ。
Maybe の Monoid としての性質をつかって mappend。 mappend は Just の中身に適用される関数で、ここでは文字列(つまり文字のリスト)が Just の中身だから文字列が連結される。よって Nothing や Just "Fizz"、 Just "Buzz"、 Just "FizzBuzz" のはいったリストをつくりだせる。
そして Maybe の MonadPlus としての性質をつかって mplus。 mplus は、ふたつの Maybe を受け取り、先に Just になった値を返す(か、どちらも Nothing なら Nothing を返す)。
だから、先に mappend した Maybe リストのうち Nothing になるところが、 Just (show n) で置き換えられて、結果、ほしかったリストができあがるという仕組み。
アイデアはいいとおもうんだけれどなあ。一ヶ月経ったら、たぶん自分も読めない。