あどけない話

インターネットに関する技術的な話など

Monadとして抽象化すると何が嬉しいの?

The Typeclassopediaには、以下のような文章があります。

結局、あらゆる誇大広告にもかかわらず、Monadは単なる型クラスに過ぎません。

また、The Trivial Monadでは、以下のように述べられています。

HaskellMonad は型クラスの1つです。Haskell の型クラスは、複数の型で共通する API を定めます。だから、Monad という型クラスとは、型の集合に対する共通の API です。

共通の API とは、return と (>>=) のことです。

こう言われると、すぐに「その共通のAPIを使うと何が嬉しいの?」という疑問が湧くでしょう。もちろん、共通の API を使う嬉しさは、後から型を変えたときに、実装を変えなくてもいいことです。この記事では、その一例をお見せしましょう。

私が「Monad で実装してよかった」と感じたことがあるのはパーサーですので、例としてパーサーを取り上げます。実装は、記事の最後に示してあります。

Maybe を使ったパーサー

Monad は文脈を表すと言われます。

Maybe は「失敗するかもしれない計算」という文脈を表します。言い換えると、成功し続ければ計算は続くが、失敗したならそこで終わりという、決定性を持つ計算です。

パーサーを Maybe を利用して実装してみましょう。

data Parser a = Parser { parse :: String -> Maybe (a,String) }

このパーサーでは、たとえ他にマッチする候補があったとしても、返ってくる結果は1つだけです。

parse (string "f" <|> string "foo") "foo"
→ Just ("f","oo")

リストを使ったパーサー

リストは、「非決定性」という文脈を表します。遅延評価の Haskell では、こんな難しい説明は不要で、単に全探索するという意味です。(リストは遅延するので、最初の候補だけを利用するなら、他の候補は探索されません。)

パーサーの定義を Maybe からリストに変えてみましょう。

data Parser a = Parser { parse :: String -> [(a,String)] }

このパーサーは、実装をまったく変更せずに動きますし、期待通りに全探索してくれます。

parse (string "f" <|> string "foo") "foo"
→ [("f","oo"),("foo","")]

百聞は一見にしかずの気持ちになれましたか?

パーサーの実装

module Parser where

import Control.Monad
import Control.Applicative

----------------------------------------------------------------

data Parser a = Parser { parse :: String -> Maybe (a,String) }
--data Parser a = Parser { parse :: String -> [(a,String)] }

----------------------------------------------------------------

instance Functor Parser where
    f `fmap` p = return f <*> p

instance Applicative Parser where
    pure  = return
    (<*>) = ap
    
instance Alternative Parser where
    empty = mzero
    (<|>) = mplus

instance Monad Parser where
    return a = Parser $ \cs -> return (a,cs)
    p >>= f  = Parser $ \cs -> parse p cs >>= \(a,cs') -> parse (f a) cs'

instance MonadPlus Parser where
    mzero       = Parser $ \_  -> mzero
    p `mplus` q = Parser $ \cs -> parse p cs `mplus` parse q cs

----------------------------------------------------------------

item :: Parser Char
item = Parser f
  where
    f []     = mzero
    f (c:cs) = return (c,cs)

----------------------------------------------------------------

satisfy :: (Char -> Bool) -> Parser Char
satisfy f = item >>= check
  where
    check c
      | f c       = return c
      | otherwise = mzero

char :: Char -> Parser Char
char c = satisfy (c ==)

----------------------------------------------------------------

string :: String -> Parser String
string []     = return []
string (c:cs) = (:) <$> char c <*> string cs