Haskellには抽象的な高階関数や演算子がいくつもあり、たまにそれらを巧妙に用いたコードがでてきて感心することがあります。
他の人が書いたHaskellのコードを読んでいると、なかなか面白いものと遭遇したりします。
巧妙に書かれたコードを解読していくと、実は型クラスのinstanceをうまく組み合わせて使っていて、とてもよい教材になることがあります。
実際にアプリケーションコードを書いていてここまで技巧的なコードを書くわけではありません。しかし、こういうコードを読み解くのは型クラスのいい練習になりますし、それまで知らなかったinstanceと遭遇したりしたときは、とても勉強になるのです。
このエントリーでは、とても技巧的なFizzBuzzを紹介し、それを読み解いていく方法を紹介します。
Haskellの初心者向けに、どういうふうに関数や型を調べて言ったらいいかを丁寧に書いています。
Haskellの難しいコード見ても何から手を付けていいか分からないという方や、そもそもHaskellのコード読む時ってどうやってリファレンスを引くの？という方には、ぜひ関数や型クラスなどを調べる方法を身につけて欲しいと思います。
注意: この記事の内容は古くなっていますが、当時のままあえて書き直していませんのでご注意ください。<> は現在は Data.Semigroup の演算子です。
目次
Twitterを眺めていたらCAMPHOR- Advent Calendarの26日目の記事が流れてきて、Haskellに関する内容だったので開いて読んでいました。
ryota-ka.hatenablog.com
この記事ではMonad (Either a)の>>=演算子を使ってうまく結果を集めていますね。
自分もEitherとかMonadとか使ったおもしろFizzBuzzを書いてみようとしましたが、結局うまく書けませんでした。
import Data.Maybe (catMaybes, listToMaybe)
main = mapM_ (print . fizzbuzz) [1..100]
fizzbuzz n = concat $ catMaybes [ listToMaybe [ "Fizz" | n `mod` 3 == 0 ], listToMaybe [ "Buzz" | n `mod` 5 == 0 ] ]
catMaybes :: [Maybe a] -> [a] を使ってmod 3とmod 5の結果を集めてみましたが、この後どうすればいいかよく分かりませんでした。
ここでconcatを使わずにlistToMaybeを用いると、15の倍数のBuzzが落ちてしまいます。
かと言って""をまたNothingにマップするString -> Maybe Stringを書くのも、なんか一旦Stringに落としたものをまた持ち上げている感じがして嫌な気分です。
[] -> Nothing でそれ以外の時は関数をかますことができる、[a] -> ([a] -> b) -> Maybe bを書こうかと思いましたが、どうもキレイじゃない気がします。
綺麗に書けなくて困ったので、Beautiful FizzBuzz in Haskellとかで適当にググってカッコイイFizzBuzzを探していたところ、とても興味深いFizzBuzzを見つけました。
I finally bothered to implement FizzBuzz. I would fail the interview anyway, though...
let (m ~> str) x = str <$ guard (x `mod` m == 0)
in map (fromMaybe . show <*> 3 ~> "fizz" <> 5 ~> "buzz")
reddit Haskell: I Did A Haskell: fizzbuzz
なるほど、わからん
何をやっているかさっぱり分かりませんね。(<>) や (<*>) など、平均的なHaskellerが普段から使っている演算子でも、このコードになるとなんでここに使えるのか、型はどうやって合致しているのか、すぐには理解できないと思います。
一体どんな仕組みでこのコードが成り立っているのか、これを書いた人はどうやってこのコードを組み立てたのか、調べてみましょう。
コードを理解しよう
まずは必要なモジュールなどを含め、実行できる形にコードを整えてみました。
(GHC 7.10.x以降をお使いの方は、Control.ApplicativeとData.Functorのimportは不要です。)
import Control.Applicative ((<*>))
import Control.Monad (guard)
import Data.Functor ((<$))
import Data.Maybe (fromMaybe)
import Data.Monoid ((<>))
main :: IO ()
main = mapM_ (putStrLn . fizzbuzz) [1..100]
fizzbuzz :: Integer -> String
fizzbuzz = let (d ~> s) n = s <$ guard (n `mod` d == 0)
in fromMaybe . show <*> 3 ~> "Fizz" <> 5 ~> "Buzz"
このコードを実行すると、きちんとFizzBuzzが表示されます。
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
...
よさそうですね。
ちゃんとFizzBuzzになっています。
それでは、このコードがどういう仕組みで動いているのか調べてみましょう。
まずはletのところからです。
fizzbuzz = let (d ~> s) n = s <$ guard (n `mod` d == 0)
in fromMaybe . show <*> 3 ~> "Fizz" <> 5 ~> "Buzz"
演算子(~>)を定義しています。
ghciで丁寧に、この演算子の型と動作を見ていきます。
$ ghci
GHCi, version 7.10.2: http://www.haskell.org/ghc/ :? for help
Prelude> let (d ~> s) n = s <$ guard (n `mod` d == 0)
<interactive>:2:23: Not in scope: ‘guard’
Prelude> :!hoogle guard | head -n 1
Control.Monad guard :: MonadPlus m => Bool -> m ()
Prelude> import Control.Monad
Prelude Control.Monad> let (d ~> s) n = s <$ guard (n `mod` d == 0)
定義できたので使ってみましょう。 ((<$)がないと言われる場合は、:import Data.Functorして下さい)
Prelude Control.Monad> (3 ~> "Fizz") 1
<interactive>:21:1:
No instance for (Show (f0 [Char])) arising from a use of ‘print’
The type variable ‘f0’ is ambiguous
Note: there are several potential instances:
instance (Show a, Show b) => Show (Either a b)
instance Show a => Show (Maybe a)
instance (Integral a, Show a) => Show (GHC.Real.Ratio a)
...plus 15 others
In a stmt of an interactive GHCi command: print it
型を限定してあげないと表示できないか…
なになに、f0が曖昧？うーん、まぁ左のほうでfromMaybeとかやってるしMaybeでしょうね。
Prelude Control.Monad> (3 ~> "Fizz") 1 :: Maybe String
Nothing
Prelude Control.Monad> (3 ~> "Fizz") 3 :: Maybe String
Just "Fizz"
Prelude Control.Monad> map (3 ~> "Fizz") [1..20] :: [Maybe String]
[Nothing,Nothing,Just "Fizz",Nothing,Nothing,Just "Fizz",Nothing,Nothing,Just "Fizz",Nothing,Nothing,Just "Fizz",Nothing,Nothing,Just "Fizz",Nothing,Nothing,Just "Fizz",Nothing,Nothing]
なるほど。
この演算子がやっていることはすぐに理解できますね。3 ~> "Fizz"は、「3の時だけJust "Fizz"になる」関数です。
型を見てみましょう。
Prelude Control.Monad> :t (3 ~> "Fizz")
(3 ~> "Fizz")
:: (Integral a1, GHC.Base.Alternative f) => a1 -> f [Char]
Prelude Control.Monad> :t ((3 ~> "Fizz") :: Integer -> Maybe String)
((3 ~> "Fizz") :: Integer -> Maybe String) :: Integer -> Maybe String
(3 ~> "Fizz") :: Integer -> Maybe String ですね。
つまり、(~>)の型は
Prelude Control.Monad> :t (~>)
(~>)
:: (Integral a1, GHC.Base.Alternative f) => a1 -> a -> a1 -> f a
Prelude Control.Monad> :t (~>) :: Integer -> String -> Integer -> Maybe String
(~>) :: Integer -> String -> Integer -> Maybe String
:: Integer -> String -> Integer -> Maybe String
です。
単に:t 演算子するだけでは、量化されたよく分からない型が表示されますが、
明示的に :: T とつけてやれば、それで型チェックが通るかどうか確かめることができます。
それでは、(~>)の中で型が合っていることを確かめます。
Prelude Control.Monad> :t guard
guard :: GHC.Base.Alternative f => Bool -> f ()
Prelude Control.Monad> :t (<$)
(<$) :: Functor f => a -> f b -> f a
guardはf ()を返します。このfは、Maybeに違いありません。ということは…
Prelude Control.Monad> :t (guard :: Bool -> Maybe ())
(guard :: Bool -> Maybe ()) :: Bool -> Maybe ()
Prelude Control.Monad> :t (<$) :: String -> Maybe () -> Maybe String
(<$) :: String -> Maybe () -> Maybe String
:: String -> Maybe () -> Maybe String
なるほど。ようやく登場人物たちの型がわかってきました。
guard :: Bool -> Maybe ()
(<$) :: String -> Maybe () -> Maybe String
(~>) :: Integer -> String -> Integer -> Maybe String
ですね。
もう一度、(~>)の定義を見てみましょう。
(~>) :: Integer -> String -> Integer -> Maybe String
(~>) d s n = s <$ guard (n `mod` d == 0)
dとnはInteger、sは"Fizz"のようなStringです。
きちんと型があっていることが目で見て分かりますね。
(分からなかったら丁寧に紙と鉛筆で確認しましょう！コードの下に線でも引いて、ここがどういう型だからちゃんと適用できるな、というふうに確認します。)
あとは(<$)とguardの動作を確認するだけです。
まず、guardから調べましょう。
Hoogleでguardを調べて、ドキュメントに飛びます。
guard :: Alternative f => Bool -> f ()
guard b is pure () if b is True, and empty if b is False.The base package: Control.Monad
Alternative、慣れていないと難しいですね。
今回の場合はguard :: Bool -> Maybe ()、すなわちf = Maybeなので、instance Alternative Maybeを探します。
上のドキュメントを開いていますか？
guardの型定義のApplicativeのところのリンクを踏んで、まずはAlternativeがどういう型クラスだったかを調べます。
class Applicative f => Alternative f where
A monoid on applicative functors.
Minimal complete definition
empty, (<|>)
The base package: Control.Applicative
Monoidですね。emptyはだいたい単位元 (mempty) で(<|>)はだいたいOR (mappend) です (かなりざっくりしたイメージです)。
少し下に、Alternative Maybeのリンクがあります。
左の+をクリックすると、Maybeがどういう風にAlternativeのinstanceなのかが分かります。しかし、なんかよくわからないですね。
そういう時は、Sourceというところをクリックしてソースコードを見ます。
instance Alternative Maybe where
empty = Nothing
Nothing <|> r = r
l <|> _ = l
なるほど、とても簡潔ですね。
だいたい、NothingはFalseで(<|>)はOR (||)のようなものです。
(||) :: Bool -> Bool -> Bool
False || r = r
l || _ = l
同じです。
さて、guardの説明は、guard b is pure () if b is True, and empty if b is False.でした。emptyの意味はinstance Alternative Maybeの定義からNothingだと分かりましたが、まだpureが何者かがよく分かっていません。
そこで、guardの説明文のpureのリンクを踏むと、Applicativeに飛びます。
Applicativeが何かはとりあえず置いておいて、instance Applicative Maybeを探してソースコードを確認します。
instance Applicative Maybe where
pure = Just
Just f <*> m = fmap f m
Nothing <*> _m = Nothing
Just _m1 *> m2 = m2
Nothing *> _m2 = Nothing
つまり、pureはJustということが分かりました。
まとめると、guardの説明をBool -> Maybe ()に限ると、次のようになります。
guard b is Just () if b is True, and Nothing if b is False.
これが本当か、ghciで確認しましょう。
Prelude Control.Monad> guard True :: Maybe ()
Just ()
Prelude Control.Monad> guard False :: Maybe ()
Nothing
確かに、そうなっていますね。
TrueならJust ()を返し、FalseならNothingを返す関数です。
この文脈において、guardはBool -> Maybe ()の同型写像ですね。
さて、(~>)の中でguardの働きが分かりました。
(~>) :: Integer -> String -> Integer -> Maybe String
(~>) d s n = s <$ guard (n `mod` d == 0)
nがdの倍数なら s <$ Just () となり、倍数でないなら s <$ Nothing となります。
(~>)の動作からすると、(<$)は、右辺がJust ()なら Just s、右辺がNothingならNothingを返すと推察されます。
それでは、(<$)の定義を見てみましょう。
Hoogleで<$を検索し、Functorのドキュメントに飛びます。
(<$) :: a -> f b -> f a
Replace all locations in the input with the same value. The default definition is fmap . const, but this may be overridden with a more efficient version.The base package: Data.Functor
なるほど、手短に言うとfmap . constだということがわかりました。
(<$)の部分を書き換えてみます。
(~>) d s n = (fmap . const) s (guard (n `mod` d == 0))
もうちょい簡約！
(~>) d s n = fmap (const s) (guard (n `mod` d == 0))
うおおおおお！ようやく見慣れた感じになりました。
guardの返り値は、Just ()かNothingなので、
fmap (const s) (Just ()) ==> Just s
fmap (const s) Nothing ==> Nothing
となることが分かります。
この動作が不安という方は、instance Functor Maybeを確認して下さい。
instance Functor Maybe where
fmap _ Nothing = Nothing
fmap f (Just a) = Just (f a)
fmapはNothingには何もせず、Justで包まれた値には関数を適用してJustで包んで返します。
このMaybe Functorはとても重要なFunctorなので、覚えておきましょう。
以上で、(~>)演算子の動きを完全に追うことができました。
let (d ~> s) n = s <$ guard (n `mod` d == 0)
3 ~> "Fizz" は、3の倍数にはNothingを返し (ここでguardの処理とinstance Applicative Maybe、(<$) = fmap . constとinstance Functor Maybeの定義をパッパッと思い出しながら動作を確認します)、引数が3の倍数ではないならJust "Fizz"を返すような関数です。
だんだんパズルの紐が解けてきました。
instance Alternative Maybe の guard :: Bool -> Maybe () で倍数かどうかというBool値からMaybe ()に写す。Data.Functorの演算子(<$) = fmap . constが使われている。ここでのFunctorのinstanceはMaybe
後半戦: 関数Applicative・関数Monoid
それでは、後半を調べていきましょう。
fromMaybe . show <*> 3 ~> "Fizz" <> 5 ~> "Buzz"
演算子が4つありますね。
(.)は頻繁に使われる関数の合成演算子で、(~>)は先程動作を確認した演算子です。
(<*>)はApplicativeの演算子で(<>)はMonoidの演算子、という知識はお持ちの方は多いでしょう。
しかし、普段使う演算子にも関わらず、このコードがなぜうまく動くのか、パッとイメージするのは難しいのではないでしょうか。
それくらい、このコードは技巧に富んでおり、エレガントで、しかもこんなにもエントリーを書いてしまうほど興味深いコードなのです。
とりあえず、fizzbuzz関数をghciで定義しましょう。
Prelude Control.Monad> let fizzbuzz = let (d ~> s) n = s <$ guard (n `mod` d == 0) in fromMaybe . show <*> 3 ~> "Fizz" <> 5 ~> "Buzz"
<interactive>:42:64: Not in scope: ‘fromMaybe’
<interactive>:42:97:
Not in scope: ‘<>’
Prelude Control.Monad> import Data.Monoid
Prelude Control.Monad Data.Monoid> import Data.Maybe
Prelude Control.Monad Data.Monoid Data.Maybe> let fizzbuzz = let (d ~> s) n = s <$ guard (n `mod` d == 0) in fromMaybe . show <*> 3 ~> "Fizz" <> 5 ~> "Buzz"
Prelude Control.Monad Data.Monoid Data.Maybe> :t fizzbuzz
fizzbuzz :: (Integral a, Show a) => a -> String
Prelude Control.Monad Data.Monoid Data.Maybe> map fizzbuzz [1..20]
["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz","16","17","Fizz","19","Buzz"]
できました。
ちゃんと動いていますね。
まず、演算子が4つもあって、どういうふうに結合しているかが定かではありません。
予想をつけることはできますが、きちんと結合の強さを確認しておきます。
Prelude Control.Monad Data.Monoid Data.Maybe> :i .
(.) :: (b -> c) -> (a -> b) -> a -> c
infixr 9 .
Prelude Control.Monad Data.Monoid Data.Maybe> :i <*>
class Functor f => Applicative (f :: * -> *) where
...
(<*>) :: f (a -> b) -> f a -> f b
...
infixl 4 <*>
Prelude Control.Monad Data.Monoid Data.Maybe> :i ~>
(~>) ::
(Integral a1, GHC.Base.Alternative f) => a1 -> a -> a1 -> f a
Prelude Control.Monad Data.Monoid Data.Maybe> :i <>
(<>) :: Monoid m => m -> m -> m
infixr 6 <>
このinfixrとかinfixlの後の数字に着目します。
この数字が大きい方が、強く結合します。
強く結合するとは、括弧を省略した時に先に結びつくということです。
例えば、1 + 2 * 3は1 + (2 * 3)となりますが、これは
Prelude> :i +
class Num a where
(+) :: a -> a -> a
...
infixl 6 +
Prelude> :i *
class Num a where
...
(*) :: a -> a -> a
...
infixl 7 *
のように、(*)演算子のほうが(+)演算子よりも結合の強さを表す数字が大きいからです。
それでは今出てきた4つの演算子の結合の強さは
infixr 9 .
infixr 6 <>
infixl 4 <*>
あれ、(~>)の結合の強さはいくらなのでしょうか？
演算子の結合の強さは我々が明示的に指定することができますが、今回の場合は何も書いていません。
書いていない時はどうなるんだったっけと思ってhaskell operator precedence rulesのような適当な単語でググります。
そうすると、The Haskell 98 Report: Declarationsが検索結果トップに出てきます (記事執筆当時) のでリンクを開き、「operator」でページ内検索します。
Any operator lacking a fixity declaration is assumed to be infixl 9 (See Section 3 for more on the use of fixities).The Haskell 98 Report: Declarations
なるほど、何も書かなかったらinfixl 9になると書いてあります。
すなわち、今回のコードでは
infixr 9 .
infixl 9 ~>
infixr 6 <>
infixl 4 <*>
なので、
(fromMaybe . show) <*> ((3 ~> "Fizz") <> (5 ~> "Buzz"))
のように結合することが、きちんと分かりました。
このFizzBuzzのコード、演算子の結合の強さを味方につけていてとても上手いですね (この演算子の強さを見たときは、本当に「あーうまいなー」と言ってにやにやしてしまいました)。
「きちんと」の意味は、なんとなく動作やコードの見た目から推測したのではなく、根拠を持って結論づけてたということです。
括弧が書かれていない式の中で演算子の挙動を調べるときは、まずは結合の強さを調べるのがポイントです。
さぁ、まず右側の動作から確認していきましょう。
(3 ~> "Fizz") <> (5 ~> "Buzz")
FizzBuzzの出力結果や、3 ~> "Fizz"をこれまで動作と型を確認してきたことから、この関数は
- 15の倍数なら
Just "FizzBuzz"
- 3の倍数なら
Just "Fizz"
- 5の倍数なら
Just "Buzz"
- 上記のどれでもないなら
Nothing
となる関数であることが推測されます。
そして、実際にそうなのです！
Prelude Control.Monad Data.Monoid Data.Maybe> let f = (3 ~> "Fizz") <> (5 ~> "Buzz")
Prelude Control.Monad Data.Monoid Data.Maybe> map f [1..20] :: [Maybe String]
[Nothing,Nothing,Just "Fizz",Nothing,Just "Buzz",Just "Fizz",Nothing,Nothing,Just "Fizz",Just "Buzz",Nothing,Just "Fizz",Nothing,Nothing,Just "FizzBuzz",Nothing,Nothing,Just "Fizz",Nothing,Just "Buzz"]
このように3の倍数の結果と5の倍数の結果を結合しつつ、Maybeを返すというのは、私もcatMaybesを使ったりいろいろごちゃごちゃして悩んで結局わからなかったところです。
一体このコードはどんなトリックを使っているのでしょうか。
ここにはMonoidがうまく使われています。
注目すべきは言うまでもなく、(<>)という演算子にあります。
(3 ~> "Fizz") :: Integer -> Maybe String であることから、今回のコードでは
(<>) :: (Integer -> Maybe String) -> (Integer -> Maybe String) -> (Integer -> Maybe String)
となっているはずです。
そこで、HoogleでMonoidと入力してData.Monoidのドキュメントに飛びます。
Monoidとは、一つの二項演算子と単位元を持つような代数的構造です。群から逆元の存在を抜いたものです。
要するに、((||), False)はMonoidだし ((++), [])も((+), 0)もMonoidです。
Monoidについては以下の記事が初心者にも丁寧に書かれているのでご参考にしてください。
itchyny.hatenablog.com
さて、今回のMonoidのinstanceは何を使っているのでしょうか。
Monoidの定義と(<>)は次のようになっています。
class Monoid a where
mempty :: a
mappend :: a -> a -> a
(<>) :: Monoid m => m -> m -> m
(<>) = mappend
現在のコード上の(<>)の型と上のMonoidの定義をじっと見比べると、Monoid (Integer -> Maybe String)を使っていることになります。
こんなの見たことありますか？ええっ、関数Monoid？とびっくりしてData.Monoidのドキュメントを確認しますと、確かにMonoid b => Monoid (a -> b)というものがあります。
Sourceをクリックしてコードを確認すると、次のようになっています。
instance Monoid b => Monoid (a -> b) where
mempty _ = mempty
mappend f g x = f x `mappend` g x
なるほど、むずかしい。関数を適用した2つを演算子にかますような関数を返すんですね。mappendの定義は、どことなくControl.Arrowの(&&&)を思い出させます。
これは本当にMonoidになっているのでしょうか。
この定義に従いますと、Monoid (a -> b)のmemptyは\_ -> memptyです (const memptyです)。
これが上記で定義された二項演算子mappendの単位元であることを確認できればOKです。
mappend (\_ -> mempty) g
==> \x -> ((\_ -> mempty) x) `mappend` g x
==> \x -> mempty `mappend` g x
==> \x -> g x (Monoid bの性質より)
==> g
mappend f (\_ -> mempty)
==> \x -> f x `mappend` ((\_ -> mempty) x)
==> \x -> f x `mappend` mempty
==> \x -> f x (Monoid bの性質より)
==> f
よって\_ -> memptyは二項演算子mappendの単位元になっていることが確かめられました。
従って、もしbがMonoidならMonoid (a -> b)を作れることが分かりました。
FizzBuzzのコードで使われている(<>)は、
(3 ~> "Fizz") <> (5 ~> "Buzz")
次のような型でした。
(<>) :: (Integer -> Maybe String) -> (Integer -> Maybe String) -> (Integer -> Maybe String)
ですからa = Integer、b = Maybe StringとなるようなMonoid (a -> b)が使われています。
ここでMonoid bとなることが要請されますが、b = Maybe Stringですから、次のようなinstanceが使われます。
instance Monoid a => Monoid (Maybe a) where
mempty = Nothing
Nothing `mappend` m = m
m `mappend` Nothing = m
Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)
Nothingが単位元、演算子はJustの中身に対して行われます。
つまりこういうことですね。
Prelude Data.Monoid> Just "Fizz" <> Just "Buzz"
Just "FizzBuzz"
Prelude Data.Monoid> Just "Fizz" <> Nothing
Just "Fizz"
Prelude Data.Monoid> Nothing <> Just "Buzz"
Just "Buzz"
Prelude Data.Monoid> Nothing <> Nothing
Nothing
ようやく謎が解けてきました。
もう一度じっとコードを見つめて
(3 ~> "Fizz") <> (5 ~> "Buzz")
instance Monoid b => Monoid (a -> b) where
mappend f g x = f x `mappend` g x
順番にどの性質を使っているか確認しながら書き換えていきます (勘の良い人は分かったところで止めてよいですよ)。
(3 ~> "Fizz") <> (5 ~> "Buzz")
==> (\n -> if n `mod` 3 == 0 then Just "Fizz" else Nothing)
<> (\n -> if n `mod` 5 == 0 then Just "Buzz" else Nothing)
==> \n -> ((if n `mod` 3 == 0 then Just "Fizz" else Nothing)
<> (if n `mod` 5 == 0 then Just "Buzz" else Nothing)) (関数Monoidのmappend)
==> \n -> (if n `mod` 3 == 0 && n `mod` 5 == 0
then Just "Fizz" <> Just "Buzz"
else if n `mod` 3 == 0 && !(n `mod` 5 == 0)
then Just "Fizz" <> Nothing
else if !(n `mod` 3 == 0) && n `mod` 5 == 0
then Nothing <> Just "Buzz"
else Nothing <> Nothing) (ifを展開)
==> \n -> (if n `mod` 3 == 0 && n `mod` 5 == 0
then Just "FizzBuzz"
else if n `mod` 3 == 0 && !(n `mod` 5 == 0)
then Just "Fizz"
else if !(n `mod` 3 == 0) && n `mod` 5 == 0
then Just "Buzz"
else Nothing) (Maybe MonoidにおいてNothingは単位元)
やっと、この関数が意図する動作をすることが確認できました (ifは展開せずともイメージできたらよいです)。
少しまとめますと、
- この
(<>)は3つのMonoidが使われている
- 一つ目は
instance Monoid [a]: ((++), [])。これのおかげで"Fizz" <> "Buzz"が"FizzBuzz"となる。
- 二つ目は
instance Monoid a => Monoid (Maybe a)。単位元はNothing。Just "Fizz" <> Just "Buzz"がJust "FizzBuzz"になる。Nothingが単位元なので、Just "Fizz" <> Nothing == Just "Fizz"になる。
- 三つ目は
instance Monoid b => Monoid (a -> b)。単位元は\_ -> mempty。3の倍数に対する関数と、5の倍数に対する関数を(<>)で結合して、これらの結果をうまくくっつけるような関数を作ることができる。
かなり巧妙にMonoidが使われていることが分かります。
最後に残ったのは、(<*>)という演算子です。
(fromMaybe . show) <*> ((3 ~> "Fizz") <> (5 ~> "Buzz"))
演算子の左辺は次のような型ですので、
Prelude Control.Monad Data.Monoid Data.Maybe> :t fromMaybe . show
fromMaybe . show :: Show a => a -> Maybe String -> String
Prelude Control.Monad Data.Monoid Data.Maybe> :t fromMaybe . show :: Integer -> Maybe String -> String
fromMaybe . show :: Integer -> Maybe String -> String
:: Integer -> Maybe String -> String
この(<*>)演算子の特化された型は次のようになるはずです。
Prelude Control.Monad Data.Monoid Data.Maybe> :t (<*>) :: (Integer -> Maybe String -> String) -> (Integer -> Maybe String) -> Integer -> String
(<*>) :: (Integer -> Maybe String -> String) -> (Integer -> Maybe String) -> Integer -> String
:: (Integer -> Maybe String -> String)
-> (Integer -> Maybe String) -> Integer -> String
きちんと型が合いましたね。
さて、(<*>)はApplicativeの演算子ですが、こういうふうな型になるinstanceは何だろうと調べます。
(<*>)の量化された型は
Prelude Control.Monad Data.Monoid Data.Maybe> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
ですので、今回使われている型と睨みながら次のように当てはめてみます。
f (a -> b) === Integer -> Maybe String -> String
f a === Integer -> Maybe String
f b === Integer -> String
なんかいやな予感がしますね… 関数かな…
Hoogleでこの演算子を調べて、Control.Applicativeのドキュメントに飛びます。
そうすると、instance Applicative ((->) a)というそれっぽいinstanceを見つけたので、慌てて紙と鉛筆を取って型が合うか確かめます。
f (a -> b) === ((->) r) (a -> b) === r -> a -> b === Integer -> Maybe String -> String
f a === ((->) r) a === r -> a === Integer -> Maybe String
f b === ((->) r) b === r -> b === Integer -> String
a === Maybe String
b === String
r === Integer
型は合いますね。
次にこのinstanceのSourceを見に行きます。
instance Applicative ((->) a) where
pure = const
(<*>) f g x = f x (g x)
なんだこれは…
f xにg xを適用するとか言っていますよ…
つまり今回の場合は
(fromMaybe . show) <*> ((3 ~> "Fizz") <> (5 ~> "Buzz"))
なので、一生懸命変形していくと
(fromMaybe . show) <*> ((3 ~> "Fizz") <> (5 ~> "Buzz"))
==> (\f g x -> f x (g x)) (fromMaybe . show) ((3 ~> "Fizz") <> (5 ~> "Buzz"))
==> (\g x -> (fromMaybe . show) x (g x)) ((3 ~> "Fizz") <> (5 ~> "Buzz"))
==> \x -> fromMaybe (show x) (((3 ~> "Fizz") <> (5 ~> "Buzz")) x)
なるほど、もう分かりましたね。
最初のfizzbuzzをこの形で書いてみます。
fizzbuzz n = let (d ~> s) n = s <$ guard (n `mod` d == 0)
in fromMaybe (show n) (((3 ~> "Fizz") <> (5 ~> "Buzz")) n)
ここまで来たら読めますね！
あとはfromMaybeという関数を知っているかどうかというだけです。
HoogleでfromMaybeを検索し、Data.Maybeのドキュメントに飛びます。
fromMaybe :: a -> Maybe a -> a
The fromMaybe function takes a default value and and Maybe value. If the Maybe is Nothing, it returns the default values; otherwise, it returns the value contained in the Maybe.The base package: Data.Maybe
つまり、デフォルトを指定してJustから安全に取り出す関数というわけです。
念のためにSourceを見に行きます。
fromMaybe :: a -> Maybe a -> a
fromMaybe d x = case x of {Nothing -> d;Just v -> v}
コードはとても簡潔で、確かにNothingならデフォルトを返してそうでないならJustを外しています。
今FizzBuzzのコードは
fromMaybe (show n) (((3 ~> "Fizz") <> (5 ~> "Buzz")) n)
となっています。fromMaybeの第二引数がJust "FizzBuzz"またはJust "Fizz"、Just "Buzz"そしてNothingを返すことを思い出すと、Justから取り出しつつNothingのときは数字をそのまま表示するshow nとなっていることが分かります。
- 演算子が出てきたら結合の強さを確認しよう。結合の強さをこちらが指定しなければ、
infixl 9になる。
Monoid三段構え。instance Monoid b => Monoid (a -> b) の単位元は\_ -> mempty。2つの関数の返り値が同じ型でかつMonoidなら、関数たちをうまくmappendすることができる。instance Applicative ((->) a) では (<*>) f g x = f x (g x) になっている。
同じコードを書いてみよう
ここまでは、すでにあるコードを読み解く方法を説明してきました。
しかし、これを書いた人は、どのようにこのコードを書いたのでしょうか。
きっと私たちにも理解できる試行錯誤で、同じコードを組み立てることができるはずです。
これを書けるためにはどういうことができればいいか、どういうことは知っていなければいけないかを確かめてみましょう。
まず、fizzbuzz関数はInteger -> Stringを作ることにしましょう (オリジナルはこれをmapしたものです)。
main :: IO ()
main = mapM_ (print . fizzbuzz) [1..100]
fizzbuzz = ...
後でprintはputStrLnにしますが、コードを書いている途中は面倒なので最初はprintと書いておきます。
まず簡単なものを書いてみます。
fizzbuzz n
| n `mod` 15 == 0 = "FizzBuzz"
| n `mod` 3 == 0 = "Fizz"
| n `mod` 5 == 0 = "Buzz"
| otherwise = show n
実行したら次のようになります。
"1"
"2"
"Fizz"
"4"
"Buzz"
"Fizz"
"7"
"8"
"Fizz"
"Buzz"
"11"
"Fizz"
"13"
"14"
"FizzBuzz"
"16"
"17"
"Fizz"
"19"
"Buzz"
...
動作は大丈夫です。
さて、何度もmodと書いているので、関数にしたいですね。
また、mod 3の計算結果とmod 5の計算結果を何とかしてまとめたいです。
3の倍数ならJust 文字列を返し、そうでないならNothingを返す、そんな関数を作ってみましょう。
fizzbuzz n = (show n, f n 3 "Fizz", f n 5 "Buzz")
f n d s = if n `mod` d == 0 then Just s else Nothing
実行してみます。
("1",Nothing,Nothing)
("2",Nothing,Nothing)
("3",Just "Fizz",Nothing)
("4",Nothing,Nothing)
("5",Nothing,Just "Buzz")
("6",Just "Fizz",Nothing)
("7",Nothing,Nothing)
("8",Nothing,Nothing)
("9",Just "Fizz",Nothing)
("10",Nothing,Just "Buzz")
("11",Nothing,Nothing)
("12",Just "Fizz",Nothing)
("13",Nothing,Nothing)
("14",Nothing,Nothing)
("15",Just "Fizz",Just "Buzz")
("16",Nothing,Nothing)
("17",Nothing,Nothing)
("18",Just "Fizz",Nothing)
("19",Nothing,Nothing)
("20",Nothing,Just "Buzz")
...
ちゃんとできていますね。
modが一箇所になっていい感じです。
さぁこの結果を集約していきましょう。
まず3の倍数かつ5の倍数、すなわち
("15",Just "Fizz",Just "Buzz")
の二つ目と三つ目をJust "FizzBuzz"にしたいと考えます。
どちらか一方がNothingだったら他方を採用する… これはMonoidだと気が付きます。
Monoidの演算子(<>)を使えることを確認します。
$ ghci
GHCi, version 7.10.2: http://www.haskell.org/ghc/ :? for help
Prelude> import Data.Monoid
Prelude Data.Monoid> Just "Fizz" <> Just "Buzz"
Just "FizzBuzz"
Prelude Data.Monoid> Just "Fizz" <> Nothing
Just "Fizz"
Prelude Data.Monoid> Nothing <> Just "Buzz"
Just "Buzz"
Prelude Data.Monoid> Nothing <> Nothing
Nothing
いけそうですね！
早速この演算子を使ってみます。
fizzbuzz n = (show n, f n 3 "Fizz" <> f n 5 "Buzz")
("1",Nothing)
("2",Nothing)
("3",Just "Fizz")
("4",Nothing)
("5",Just "Buzz")
("6",Just "Fizz")
("7",Nothing)
("8",Nothing)
("9",Just "Fizz")
("10",Just "Buzz")
("11",Nothing)
("12",Just "Fizz")
("13",Nothing)
("14",Nothing)
("15",Just "FizzBuzz")
("16",Nothing)
("17",Nothing)
("18",Just "Fizz")
("19",Nothing)
("20",Just "Buzz")
...
うまくいってます！
そして、右側がNothingの時にのみ左側を採用したら良さそうです。
Justから中身を取り出しつつ安全な… fromMaybeですね！
fizzbuzz n = fromMaybe (show n) (f n 3 "Fizz" <> f n 5 "Buzz")
"1"
"2"
"Fizz"
"4"
"Buzz"
"Fizz"
"7"
"8"
"Fizz"
"Buzz"
"11"
"Fizz"
"13"
"14"
"FizzBuzz"
"16"
"17"
"Fizz"
"19"
"Buzz"
...
やったー！
うまくいきました。
ここからは、更にコードを難読化洗練させていきます。
f n d s = if n `mod` d == 0 then Just s else Nothing
まずif .. then .. elseを辞めたいですね。
BoolからMaybe Stringになるような関数、そんなものありましたっけ。
勘で Bool -> Maybe String、いや Bool -> Maybe a のほうが良さそうかなと思ってHoogleで検索します。
Justも違う、returnも違う… 第一引数がBoolのやつは… fromBool違う… お、guard？これなんだっけ…
guard :: MonadPlus m => Bool -> m ()
と思って、定義を見に行きます (今回たまたまMaybe aでヒットしてしまいましたが、思うように見つからないときはどんどん一般化させてBool -> m aのように検索します)。
guard :: Alternative f => Bool -> f ()
guard b is pure () if b is True, and empty if b is False.The base package: Control.Monad
instance Applicative Maybeを調べつつ、ghciで確認してみます。
Prelude Control.Monad> guard True :: Maybe ()
Just ()
Prelude Control.Monad> guard False :: Maybe ()
Nothing
なるほど。
f n d s = if guard (n `mod` d == 0) == Just () then Just s else Nothing
Just ()ならJust s、NothingならNothingなので、fmapだとすぐに気が付きます。
f n d s = fmap (const s) (guard (n `mod` d == 0))
"1"
"2"
"Fizz"
"4"
"Buzz"
"Fizz"
"7"
...
guardを使ってifを消せました！
そして、constしてfmap… fmap . const… (<$)ですね！
これは流石に知っておかないと気がつけません。
少し動作を確認しておきましょう。
Prelude> 1 <$ Just 0
Just 1
Prelude> 1 <$ Nothing
Nothing
Prelude> 1 <$ [1..5]
[1,1,1,1,1]
Prelude> 1 <$ Left 0
Left 0
Prelude> 1 <$ Right 0
Right 1
ふむふむ、なるほど。
Functor素晴らしいですね。
この演算子を使うと、次のようになりました。
f n d s = s <$ guard (n `mod` d == 0)
できましたね！
次は、fizzbuzz関数本体をpoint-freeスタイルに変形しましょう。
fizzbuzz n = fromMaybe (show n) (f n 3 "Fizz" <> f n 5 "Buzz")
引数のnを消したいです。
まず、後ろ側のところでnが第1引数に来ているのが難しいので、最後に来るようにfを変更します
fizzbuzz n = fromMaybe (show n) (f 3 "Fizz" n <> f 5 "Buzz" n)
f :: Integer -> String -> Integer -> Maybe String
f d s n = s <$ guard (n `mod` d == 0)
fの型も書いてみました。f 3 "Fizz"はInteger -> Maybe Stringですね。
ここで、関数のMonoidを思い出します。これもやはり知っていないとできませんね。
instance Monoid b => Monoid (a -> b) where
mempty _ = mempty
mappend f g x = f x `mappend` g x
まさに f 3 "Fizz" n <> f 5 "Buzz" n の部分がこの形になっています！
よって、次のようにも書けます。
fizzbuzz n = fromMaybe (show n) ((f 3 "Fizz" <> f 5 "Buzz") n)
show nのnが深いところにあるので、少し変形します。
fizzbuzz n = ((fromMaybe . show) n) ((f 3 "Fizz" <> f 5 "Buzz") n)
nが二回使われています。f n (g n)の形です。
うーんと考えて、Applicative ((->) a)やMonad ((->) r)などを調べます。
instance Applicative ((->) a) where
pure = const
(<*>) f g x = f x (g x)
instance Monad ((->) r) where
return = const
f >>= k = \r -> k (f r) r
今回はApplicativeの方ですね。
fizzbuzz n = ((fromMaybe . show) <*> (f 3 "Fizz" <> f 5 "Buzz")) n
最後にη変換です！
fizzbuzz = (fromMaybe . show) <*> (f 3 "Fizz" <> f 5 "Buzz")
やりました！point-freeスタイルになりました！
関数fをfizzbuzzの中に入れて
fizzbuzz = let f d s n = s <$ guard (n `mod` d == 0)
in (fromMaybe . show) <*> (f 3 "Fizz" <> f 5 "Buzz")
それっぽい演算子に書き換えつつ、恐る恐る括弧を外し、printをputStrLnにしたら完成です！
main :: IO ()
main = mapM_ (putStrLn . fizzbuzz) [1..100]
fizzbuzz :: Integer -> String
fizzbuzz = let (d ~> s) n = s <$ guard (n `mod` d == 0)
in fromMaybe . show <*> 3 ~> "Fizz" <> 5 ~> "Buzz"
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
...
やったー！！！
なんとか元のコードを再構築することができました！
気合と根性といくつかの知識が必要ですね。
- とにかくがんばる。とにかくpoint-freeスタイル。
- 困っても
Arrowに頼りすぎない。とりあえずMonadとかApplicativeなどからそれっぽいのを探す。((->) a)に注目しよう。
Monoid便利。超便利。便利すぎる。
まとめ
Monoid・Functor・Applicative・Alternative、そしてMonad。
型クラスはHaskellの特徴的な機能であり、とても便利なものです。
型クラスは我々のコードを量化し、またコードを書くときにはどういう構造のどういう性質を使っているかを意識させてくれます。
私はHaskellの様々な機能に魅了されて使っていますが、型クラスの機能がもしなかったらここまで惹かれることはなかったかもしれません。
point-freeスタイルは常にいいものではありません。
時にはコードを難解にし、読めないものにしてしまいます。
私は一時期Arrowのcombinatorを使ったpoint-freeスタイルに没頭した時期がありましたが、しばらくして熱が冷めてしまい、残ったのは全く読めない難解なコードばかりでした。
しかし、もちろん積極的に使うべきケースだって多々あります。
\x -> f (g x)よりもf . gのほうが読みやすく、「2つの関数を順番に適用する」という意味もはっきりしています。
また、do { a <- m1; b <- m2; return (f a b) }よりも f <$> m1 <*> m2 のほうが、本当に何をやりたいのかということに集中してコードを書くことができます。
いちいち case ... of を使っていたところを、 Alternative Maybe の (<|>) でサラッと書けたときは快感です。
型クラスのメソッドを意味のある用途で使い、コードが簡潔になるならば、それは推奨されてよいでしょう。
複雑なコードを解読していくのは、とても楽しいパズルです。
時には便利なinstanceを発見したり、型クラスへの理解が更に深まることもあります。
抽象的な高階関数をここまで自在に扱える言語は他にはないと思います。
技巧的すぎて実際には書かないし役に立たないなどと言わず、たまには頭の体操と思って仕組みを調べてみてはいかがでしょうか。
