parsing - Maybe を使用したエラー検出とレポート

Question

Haskell で命題論理パーサーを作成しています。私は今のところ、学習演習として手作業で構文解析を行っています。いよいよパーセクに挑みます。それまでの間、私はモナドに頭を悩ませようとしています。特に、関数Maybeからのエラーを報告するために使用していparseます。私の現在の問題は、ヘルパー関数の一部にあります:

parse' :: String -> (Maybe Wff, String)
parse' ('[':rest) = (x, if null rest''
                        then ""
                        else tail rest'')
        where (a, rest') = parse' rest
              (b, rest'') = parse' (if null rest'
                                    then ""
                                    else tail rest')
              x = if null rest'
                     || null rest''
                     || head rest' /= '|'
                     || head rest'' /= ']'
                  then Nothing
                  else Or <$> a <*> b

(参考までに、完全なparse機能はここにあります。)

このコードは、とが任意の命題[ A | B ]であるという形式の命題を解析します。ご覧のとおり、前の再帰呼び出しの結果が. これにより、状態から取り出して取り出すことができました。またはのインスタンスを使用して、この残りの部分を折りたたむにはどうすればよいですか?ABNothingNothinga == Nothingb == NothingifApplicativeMonadMaybeif

score 5 · Accepted Answer

私は実際に問題を逆方向に実行します: モナド解法から始めて、それから手巻き解法まで逆方向に作業します。これにより、手動で正しいソリューションにたどり着いた場合と同じコードが生成されます。

モナドパーサーの典型的な型シグネチャは次の形式です。

type Parser a = String -> Maybe (a, String)

Stringの外側にファイナルがあるフォームとのわずかな違いに注意してくださいMaybe。Stringどちらも有効ですが、解析が失敗した場合、残り物は無効であると考えるので、私はこの形式をより好みます。

このタイプは、実際にはの特殊なケースであり、次のStateTように定義されています。

newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }

選択した場合、次のことに注意してください。

s = String
m = Maybe

...Parserタイプを返します:

type Parser a = StateT String Maybe a

-- or: type Parser = StateT String Maybe

これの優れている点は、1 つの文字を取得するパーサーを手動で 1 つ定義するだけでよいことです。

anyChar :: Parser Char
anyChar = StateT $ \str -> case str of
    []   -> Nothing
    c:cs -> Just (c, cs)

StateTラッパーを削除すると、のタイプは次のようにanyCharなることに注意してください。

anyChar :: String -> Maybe (Char, String)

ラップすると、次のStateTようになります。

anyChar :: StateT String Maybe Char

...これはただParser Charです。

プリミティブパーサーを取得したら、StateTのMonadインターフェイスを使用して他のすべてのパーサーを定義できます。たとえば、単一の文字に一致するパーサーを定義しましょう。

import Control.Monad

char :: Char -> Parser ()
char c' = do
    c <- anyChar
    guard (c == c')

それは簡単でした！モナドguardのインスタンスが必要ですが、すでに存在しています。MonadPlusその理由は、次の 2 つのMonadPlusインスタンスのおかげです。

instance (MonadPlus m) => MonadPlus (StateT s m) where ...

instance MonadPlus Maybe where ...

これら 2 つのインスタンスの組み合わせは、がStateT s Maybe自動的にを実装するMonadPlusことを意味しますguard。

これら 2 つのパーサーがあれば、最終的なパーサーは非常に簡単に記述できます。

data Wff = Or Char Char deriving (Show)

parseWff :: Parser Wff
parseWff = do
    char '['
    a <- anyChar
    char '|'
    b <- anyChar
    char ']'
    return (Or a b)

その方がはるかに明確で、何が起こっているのかを理解するのが簡単です。それも機能します：

>>> runStateT parseWff "[A|B]"
Just (Or 'A' 'B',"")

逆算

これは、元の質問につながります: 同じ動作をどのように手書きしますか? インスタンスからさかのぼって、Monad内部MonadPlusで何をしているのかを推測します。

これを行うには、基底モナドがであるときに、MonadとのMonadPlusインスタンスが何に還元されるかを推測する必要があります。のインスタンスから始めましょう:StateTMaybeMonadStateT

instance (Monad m) => Monad (StateT s m) where
    return r = StateT (\s -> return (r, s))

    m >>= f  = StateT $ \s0 -> do
        (a, s1) <- runStateT m s0
        runStateT (f a) s1

基本モナドの一般的な用語で定義されていることに注意してください。これは、上記のコードが行うことを導出するMonadためにのインスタンスも必要であることを意味します。Maybe

instance Monad Maybe where
    return  = Just

    m >>= f = case m of
        Nothing -> Nothing
        Just a  -> f a

Maybeモナドインスタンスをモナドインスタンスに置き換えると、次のStateTようになります:

instance Monad (StateT s Maybe) where
    return r = StateT (\s -> Just (r, s))

    m >>= f  = StateT $ \s0 -> case runStateT m s0 of
        Nothing      -> Nothing
        Just (a, s1) -> runStateT (f a) s1

Monadのインスタンスを導出するために同じことを行うことができますStateT s Maybe。と`たぶんMonadPlus:StateT

instance (MonadPlus m) => MonadPlus (StateT s m) where
    mzero = StateT (\_ -> mzero)
    mplus (StateT f) (StateT g) = StateT (\s -> mplus (f s) (g s))

instance MonadPlus Maybe where
    mzero = Nothing
    mplus m1 m2 = case m1 of
        Just a  -> Just a
        Nothing -> case m2 of
            Just b  -> Just b
            Nothing -> Nothing

...そしてそれらを1つに結合します：

instance MonadPlus (StateT s Maybe) where
    mzero = StateT (\_ -> Nothing)
    mplus (StateT f) (StateT g) = StateT $ \s -> case f s of
        Just a  -> Just a
        Nothing -> case g s of
            Just b  -> Just b
            Nothing -> Nothing

これで、パーサーが内部で何をしているかを導き出すことができます。charパーサーから始めましょう。

char c' = do
    c <- anyChar
    guard (c == c')

これにより、次の脱糖が行われます。

char c' = anyChar >>= \c -> guard (c == c')

(>>=)forの機能を導き出したStateT s Maybeので、それを次のように置き換えます。

char c' = StateT $ \str0 -> case runStateT anyChar str0 of
        Nothing      -> Nothing
        Just (a, str1) -> runStateT ((\c -> guard (c == c')) a) str1

の定義はすでにわかっているanyCharので、次のように置き換えてみましょう。

char c' = StateT $ \str0 -> case runStateT (StateT $ \str -> case str of
        []   -> Nothing
        c:cs -> Just (c, cs) ) str0 of
    Nothing -> Nothing
    Just (a, str1) -> runStateT ((\c -> guard (c == c')) a) str1

runStateTがの逆であることもわかっているStateTので、次のようになります。

char c' = StateT $ \str0 -> case (\str -> case str of
        []   -> Nothing
        c:cs -> Just (c, cs) ) str0 of
    Nothing -> Nothing
    Just (a, str1) -> runStateT ((\c -> guard (c == c')) a) str1

次に、ラムダを次のように適用できますstr0。

char c' = StateT $ \str0 -> case (case str0 of
        []   -> Nothing
        c:cs -> Just (c, cs) ) of
    Nothing -> Nothing
    Just (a, str1) -> runStateT ((\c -> guard (c == c')) a) str1

ここで、外側の case ステートメントを内側の case ステートメントに分散させます。

char c' = StateT $ \str0 -> case str0 of
    []   -> case Nothing of
        Nothing -> Nothing
        Just (a, str1) -> runStateT ((\c -> guard (c == c')) a) str1
    c:cs -> case Just (c, cs) of
        Nothing -> Nothing
        Just (a, str1) -> runStateT ((\c -> guard (c == c')) a) str1

... そして case ステートメントを評価します。

char c' = StateT $ \str0 -> case str0 of
    []   -> Nothing
    c:cs -> runStateT ((\c -> guard (c == c')) c) cs

次に、ラムダをc次のように適用できます。

char c' = StateT $ \str0 -> case str0 of
    []   -> Nothing
    c:cs -> runStateT (guard (c == c')) cs

それをさらに単純化するには、何が機能するかを知る必要がguardあります。そのソースコードは次のとおりです。

guard pred = if pred then return () else mzero

何が何であるかはすでにわかっているreturnので、それらを次のように置き換えましょう。mzeroStateT s Maybe

guard pred = if pred then StateT (\s -> Just ((), s)) else StateT (\_ -> Nothing)

これを関数にインライン化できます。

char c' = StateT $ \str0 -> case str0 of
    []   -> Nothing
    c:cs -> runStateT (if (c == c')
        then StateT (\s -> Just ((), s))
        else StateT (\_ -> Nothing) ) cs

それを分配runStateTすると、次のようになります。

char c' = StateT $ \str0 -> case str0 of
    []   -> Nothing
    c:cs -> (if (c == c')
        then (\s -> Just ((), s))
        else (\_ -> Nothing) ) cs

同様に、両方のブランチをに適用できますcs。

char c' = StateT $ \str0 -> case str0 of
    []   -> Nothing
    c:cs -> if (c == c') then Just ((), cs)  else Nothing

Monadこれは、またはMonadPlusインスタンスをまったく使用していなければ、手動で記述した同等のコードです。

最後のパーサー

最後の関数についてもこのプロセスを繰り返しますが、導出は演習として残します。

parseWff = do
    char '['
    a <- anyChar
    char '|'
    b <- anyChar
    char ']'
    return (Or a b)

parseWff = StateT $ \str0 -> case str0 of
    []     -> Nothing
    c1:str1 -> if (c1 == '[')
        then case str1 of
            []      -> Nothing
            c2:str2 -> case str2 of
                []      -> Nothing
                c3:str3 -> if (c3 == '|')
                    then case str3 of
                        []      -> Nothing
                        c4:str4 -> case str4 of
                            []      -> Nothing
                            c5:str5 -> if (c5 == ']')
                                then Just (Or c2 c4, str5)
                                else Nothing
                    else Nothing
        else Nothing

...しかし、それをさらに単純化して次のようにすることができます。

parseWff = StateT $ \str0 -> case str0 of
    '[':c2:'|':c4:']':str5 -> Just (Or c2 c4, str5)
    _                      -> Nothing

tailあなたが書いた関数とは異なり、これは部分的な関数や不完全なパターンマッチを使用していないことに注意してください。また、あなたが書いたコードはコンパイルされませんが、コンパイルされたとしても、依然として間違った動作をします。

score 4 · Accepted Answer

Control.Monad呼び出された関数を使用できますguard。これは少し変わったタイプです:

guard :: MonadPlus m => Bool -> m ()

MonadPlus「空の」ケースを持つすべてのモナドをカバーします。リストの場合、これは[]; です。Maybe_ ブール値を取ります。である場合、この空の値に評価されます。それ以外の場合はに評価されます。この動作は、表記法で最も役立ちます。NothingguardFalsereturn ()do

x = do guard (not $ null rest' || null rest'' || head rest' /= '|' || head rest'' /= ']')
       Or <$> a <*> b

ここで起こることは単純です。条件がに評価された場合True、guard はを返しJust ()、これは無視されOr <$> a <*> bます (表記法がそのようにdo機能するため)。ただし、条件がの場合False、をguard返しますNothing。これは、表記の残りの部分に伝播して、まさに希望どおりdoの : という最終結果が得られます。Nothing

whereコードを読みやすくするために、ブロック内の独自の変数に条件を引き出します。

score 0 · Accepted Answer

@TikhonJelvisの回答に基づいて、関数全体を改良しましたparse。( parse'OP の関数はのwhere節にありparseます。) 最初のリビジョンでは、do 表記と `guard を使用します。

parse :: String -> Maybe Wff
parse s = do
  (x, rest) <- parse' s
  guard $ null rest
  Just x
    where  parse' ('~':rest) = do
             guard . not $ null rest
             (a, rest') <- parse' rest
             Just (Not a, rest')
           parse' ('[':rest) = do
             guard . not $ null rest
             (a, rest') <- parse' rest
             guard . not $ null rest'
             guard $ head rest' == '|'
             (b, rest'') <- parse' $ tail rest'
             guard . not $ null rest''
             guard $ head rest'' == ']'
             Just (a `Or` b, tail rest'')
           parse' (c:rest) = do
             guard $ isLower c
             Just (Var c, rest)
           parse' [] = Nothing

guardさらに実験を重ねた結果、の使用の 1 つを除くすべてを直接パターンマッチングに置き換えることができることがわかりました。

parse :: String -> Maybe Wff
parse s = do
  (x, "") <- parse' s
  Just x
    where  parse' ('~':rest) = do
             (a, rest') <- parse' rest
             Just (Not a, rest')
           parse' ('[':rest) = do
             (a, ('|':rest')) <- parse' rest
             (b, (']':rest'')) <- parse' rest'
             Just (a `Or` b, rest'')
           parse' (c:rest) = do
             guard $ isLower c
             Just (Var c, rest)
           parse' [] = Nothing

parsing - Maybe を使用したエラー検出とレポート

3 に答える 3

逆算

最後のパーサー

Related

Reference