Hatena::ブログ(Diary)

あどけない話

2010-12-11

Applicativeのススメ

この記事の目的は、Applicative 信者による Applicative スタイルの布教です。

簡潔に結論を述べると、

foo = do
  a <- m1
  b <- m2
  return (f a b)

のようなコードを書きたくなったら

foo = f <$> m1 <*> m2

と書きましょうということ。

合い言葉は、「do と return をなくせ!」です。

FunctorとMonadの間

Functor を特殊化した型クラスがMonadで、Monadの方が強力です。なぜなら、メソッドが増えるからです。

Functorのメソッドはfmapです。fmapの別名を (<$>) といいます。(この記事では、(<$>) と liftM を同一視します。) そして、Monadメソッドは、ご存知の通り (>>=) と return です。

FunctorとMonadの間にApplicativeあります。つまり、Functorを特殊化するとApplicativeになり、さらに特殊化するとMonadになります。Applicativeのメソッドapとpureで、apの別名は(<*>)です。この記事では、pure を return と同一視します。

Haskellコミュニティは、まずFunctorとMonadを導入し、後からApplicativeを受け入れたので、すべてのMonadインスタンスがApplicativeのインスタンスになっているとは限りません。しかし、すべてのMonadは、ちゃんと定義すれば Functor かつ Applicative になります。

たとえば、Parsec 2 の Parser は Monad かつ Functor ですが、Applicative ではありません。しかし、Parsec 3 の Parser は Applicative のインスタンスにもなっています。

この記事では、分かりやすさのため、以下のように理想化された世界を考えます。

class Functor m where
    (<$>) :: (a -> b) -> m a -> m b
class Functor m => Applicative m where
    pure :: a -> m a
    (<*>) :: m (a -> b) -> m a -> m b
class Applicative m => Monad m where
    (>>=) :: m a -> (a -> m b) -> m b

Applicativeスタイルでは、fmap、ap、return を使わないことに注意して下さい。

Applicativeスタイルを使うメリット

Applicativeのメリットを以下にまとめます。

  • コードが奇麗になる。(そう感じるためには慣れが必要ですが。)
  • コード量が少なくなる。
  • Monadよりも力の弱いので、安全になる。
  • Monadのように複雑なことができないので、データ設計の間違いに気付ける。

上2つについては、すでに例を見せました。もう一度書きますので、(<$>) や (<*>) を頭の中で消去して読んで下さい。

foo = f <$> m1 <*> m2

f m1 m2 という関数適用の形になっていますね。これが Applicative (適用できる)という名前の由来です。

最後のメリットは、実際に使ってみないと分からないでしょう。

Applicativeスタイル

(<$>) の型は、

(<$>) :: (a -> b) -> m a -> m b

ですが、右二つに括弧を付けてみると

(<$>) :: (a -> b) -> (m a -> m b)

となります。

これは関数を、型(a -> b)から型(m a -> m b)に持ち上げていることに他なりません。関数を m という文脈を持つデータに適応して、m の文脈に入るのです。

一方、(<*>)の型は、

(<*>) :: m (a -> b) -> m a -> m b

です。これは m の文脈の中にある関数を m の文脈の中にあるデータに適応することに他なりません。

Haskellでは、関数がカリー化されていることを考えれば、Applicativeスタイルの一般式は、以下のようになります。

f <$> m1 <*> m2 <*> ...

これをもう一度、Monad の do 形式と比べてみて下さい。

foo = do
  a <- m1
  b <- m2
  ...
  return (f a b ...)

もう、do や return なんて書きたくなくなってきたでしょう?

ApplicativeとMonadの力の差は、どこにあるのでしょうか?構造化定理によれば、一般的な制御構造のためには、逐次、繰り返し、条件分岐が必要です。

Applicativeは、基本的に逐次の機能しかありません。他の枠組みで終了条件を判定するなら、繰り返しも可能になります。事実、sequence はApplicativeスタイルでも実現できます。

sequence :: (Applicative m,Monad m) => [m a] -> m [a]
sequence []     = pure []
sequence (c:cs) = (:) <$> c <*> sequence cs

一方、Applicativeでは条件分岐は実現できません。これについては、Applicativeの論文Applicative Programming with Effectsを参照して下さい。iffy と miffy という話で解説されています。

数式の例

Applicativeスタイルは、さまざまなところに用いられますが、パーサーの実装に使うと特に有益です。

ここではパーサーの例として、「プログラミングHaskell」に載っている数式のパーサーをParsec 3で書いてみましょう。

プログラミングHaskell

プログラミングHaskell

Applicativeスタイルを知らない人が書くと、以下のような感じになるでしょう。

import Data.Char
import Text.Parsec
import Text.Parsec.String

data Exp = Add Exp Exp | Mul Exp Exp | Nat Int deriving Show

-- expr ::= term ('+' expr | e)
expr :: Parser Exp
expr = do
    t <- term
    do
        char '+'
        e <- expr
        return (Add t e)
      <|> return t

-- term ::= factor ('*' term | e)
term :: Parser Exp
term = do
    f <- factor
    do
        char '*'
        t <- term
        return (Mul f t) 
      <|> return f

-- factor ::= '(' expr ')' | nat
factor :: Parser Exp
factor = paren <|> nat
  where
    paren = do
        char '('
        e <- expr
        char ')'
        return e

-- nat ::= '0' | '1' | ...
nat :: Parser Exp
nat = do
    c <- oneOf ['0'..'9']
    return (Nat (charToInt c))
  where
    charToInt c = ord c - ord '0'

コメントにある BNF 通りコーディングされているので、分かりやすいのですが、do や return がたくさん出てくるので、Applicative 信者には汚く見えます。

実際に、使ってみましょう。

> parseTest expr "1+2*3"
Add (Nat 1) (Mul (Nat 2) (Nat 3))
> parseTest expr "(1+2)*3"
Mul (Add (Nat 1) (Nat 2)) (Nat 3)

数式の例2

先ほどのコードをApplicativeスタイルで書き直すとこうなります。

import Control.Applicative hiding ((<|>))
import Data.Char
import Text.Parsec
import Text.Parsec.String

data Exp = Add Exp Exp | Mul Exp Exp | Nat Int deriving Show

-- expr ::= term ('+' expr | e)
expr :: Parser Exp
expr = do
    t <- term
    (Add t <$> (char '+' *> expr)) <|> pure t

-- term ::= factor ('*' term | e)
term :: Parser Exp
term = do
    f <- factor
    (Mul f <$> (char '*' *> term)) <|> pure f

-- factor ::= '(' expr ')' | nat
factor :: Parser Exp
factor = paren <|> nat
  where
    paren = char '(' *> (expr <* char ')')

-- nat ::= '0' | '1' | ...
nat :: Parser Exp
nat = Nat . charToInt <$> oneOf ['0'..'9']
  where
    charToInt c = ord c - ord '0'

それぞれのパーサーを見比べて下さい。驚くほど簡潔になったのが分かると思います。

do と pure (つまり return) が出てくるのは、条件分岐の部分なので、これらが残るのは仕方ないでしょう。

この例題では、

f <$> m

という例ばかりで、

f <$> m1 <*> m2 <*> ...

という例は出てきませんでした。僕の力量不足です。すいません。

なお、(*>) は (>>) と同じで左の値は捨てて右の値だけ活かす。(<*) はその逆です。

うまく定義された書式に対しては、Applicativeスタイルのみのパーサーが書けます。

もし、パーサーの実装で、どうしても do を使わなければならなくなったら、構文を解析しようとしている書式がうまく設計されてないのかもしれません。もし変更できるなら、書式の設計を見直すとよいでしょう。

もっと学ぶには

まず、Brent Yorgey さんが書いた The Typeclassopediaを読みましょう。

Real World Haskell の 16 章では、最初に JSON のパーサーを Monad で作り、次に Applicative スタイルに書き換える例題が載っています。

この章はおそらく Bryan O'Sullivan さんによって書かれたのでしょう。彼のブログを読むと、Brent さんから Applicative スタイルを習ったのが分かって、微笑ましいです。

僕がはじめから Applicative スタイルを指向して作ったパーサーコンビネータライブラリappar があります。よかったら参考にして下さい

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証