Haskellには抽象的な高階関数や演算子がいくつもあり、たまにそれらを巧妙に用いたコードがでてきて感心することがあります。 他の人が書いたHaskellのコードを読んでいると、なかなか面白いものと遭遇したりします。 巧妙に書かれたコードを解読していくと、実は型クラスのinstanceをうまく組み合わせて使っていて、とてもよい教材になることがあります。
実際にアプリケーションコードを書いていてここまで技巧的なコードを書くわけではありません。しかし、こういうコードを読み解くのは型クラスのいい練習になりますし、それまで知らなかったinstanceと遭遇したりしたときは、とても勉強になるのです。
このエントリーでは、とても技巧的なFizzBuzzを紹介し、それを読み解いていく方法を紹介します。 Haskellの初心者向けに、どういうふうに関数や型を調べて言ったらいいかを丁寧に書いています。 Haskellの難しいコード見ても何から手を付けていいか分からないという方や、そもそもHaskellのコード読む時ってどうやってリファレンスを引くの?という方には、ぜひ関数や型クラスなどを調べる方法を身につけて欲しいと思います。
注意: この記事の内容は古くなっていますが、当時のままあえて書き直していませんのでご注意ください。<>
は現在は Data.Semigroup
の演算子です。
目次
導入 ― おもしろいFizzBuzz
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になっています。 それでは、このコードがどういう仕組みで動いているのか調べてみましょう。
前半戦: 演算子 (~>)
・Alternative
まずは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) -- Defined in ‘Data.Either’ instance Show a => Show (Maybe a) -- Defined in ‘GHC.Show’ instance (Integral a, Show a) => Show (GHC.Real.Ratio a) -- Defined in ‘GHC.Real’ ...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 whereA monoid on applicative functors.
Minimal complete definitionempty, (<|>)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 aReplace 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 -- Defined in ‘GHC.Base’ infixr 9 . Prelude Control.Monad Data.Monoid Data.Maybe> :i <*> class Functor f => Applicative (f :: * -> *) where ... (<*>) :: f (a -> b) -> f a -> f b ... -- Defined in ‘GHC.Base’ infixl 4 <*> Prelude Control.Monad Data.Monoid Data.Maybe> :i ~> (~>) :: (Integral a1, GHC.Base.Alternative f) => a1 -> a -> a1 -> f a -- Defined at <interactive>:12:8 Prelude Control.Monad Data.Monoid Data.Maybe> :i <> (<>) :: Monoid m => m -> m -> m -- Defined in ‘Data.Monoid’ infixr 6 <>
このinfixr
とかinfixl
の後の数字に着目します。
この数字が大きい方が、強く結合します。
強く結合するとは、括弧を省略した時に先に結びつくということです。
例えば、1 + 2 * 3
は1 + (2 * 3)
となりますが、これは
Prelude> :i + class Num a where (+) :: a -> a -> a ... -- Defined in ‘GHC.Num’ infixl 6 + Prelude> :i * class Num a where ... (*) :: a -> a -> a ... -- Defined in ‘GHC.Num’ 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 -> aThe 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を発見したり、型クラスへの理解が更に深まることもあります。 抽象的な高階関数をここまで自在に扱える言語は他にはないと思います。 技巧的すぎて実際には書かないし役に立たないなどと言わず、たまには頭の体操と思って仕組みを調べてみてはいかがでしょうか。