解析器（Haskell）更好的應用實例

Question

我正在通過Brent Yorgey Haskell course，我無法爲Applicative定義一個好實例。解析器的定義如下：

newtype Parser a = Parser { runParser :: String -> Maybe (a, String) } 

該函數採用一個串，解析一定量的輸入，並返回一個也許元組，其中所述第一值是分析器的類型，和其餘的是未解析的餘數的字符串。例如，這是一個解析器的正整數：

posInt :: Parser Integer 
posInt = Parser f 
    where 
    f xs 
     | null ns = Nothing 
     | otherwise = Just (read ns, rest) 
     where (ns, rest) = span isDigit xs 

該任務是爲解析器創建一個Applicative實例。我們先從一個函子實例（這是比較直接的，我認爲）：

first :: (a -> b) -> (a,c) -> (b,c) 
first f (a, c) = (f a, c) 

instance Functor Parser where 
    fmap f p = Parser f' 
    where f' s = fmap (first f) $ (runParser p) s 

然後我在試着與應用型：

collapse (Just (Just a)) = Just a 
collapse _ = Nothing 

extract (Just a, Just b) = Just (a,b) 
extract _ = Nothing 

appliedFunc :: Parser (a->b) -> Parser a -> String -> Maybe (b, String) 
appliedFunc p1 p2 str = extract (f <*> fmap fst result2, fmap snd result2) 
    where result1 = (runParser p1) str 
     f   = fmap fst result1 
     result2 = collapse $ fmap (runParser p2) $ fmap snd result1 

instance Applicative Parser where 
    pure a = Parser (\s -> Just (a, s)) 
    p1 <*> p2 = Parser (appliedFunc p1 p2) 

...呸。所以我的問題是，我怎樣才能讓我的應用程序實例更清晰，更難讀？我覺得這個問題有一個簡單的答案，但我還沒有能夠把我的頭圍繞在類型上。

Answer 1

我假設你還沒有到Monad s的課程。你使用的方式collapse和fmap表明你本質上是重新創造了Monad來解決這個問題，尤其是Monad Maybe實例。實際上，您的collapse與此單子的join相同。確實使用是解決這個問題的一個非常優雅的方式，但是在這一點上也許有點「作弊」。以下是您在使用功能，我可以讓它進入最佳形狀：

appliedFunc p1 p2 str = collapse $ fmap step1 (runParser p1 str) 
    where 
    step1 (f, str2) = collapse $ fmap step2 (runParser p2 str2) 
     where 
     step2 (x, str3) = Just (f x, str3) 

一旦你到Monad適格，你應該能夠用更簡潔(>>=)運營商和/或do符號來改寫這個。

另一個幾乎同樣簡單但不需要重新發明monads的方法是使用Maybe的顯式模式匹配。然後你可以得到像這樣的東西：

appliedFunc p1 p2 str = case runParser p1 str of 
    Nothing  -> Nothing 
    Just (f, str2) -> case runParser p2 str2 of 
     Nothing  -> Nothing 
     Just (x, str3) -> Just (f x, str3) 

Answer 2

這可能不是你想要的，但我想順便說有實現這個一個非常簡潔的方式說：

{-# LANGUAGE GeneralizedNewtypeDeriving #-} 

import Control.Applicative 
import Control.Monad.Trans.State 

newtype Parser a = Parser { unParser :: StateT String Maybe a } 
    deriving (Functor, Applicative, Monad, Alternative) 

runParser :: Parser a -> String -> Maybe (a, String) 
runParser = runStateT . unParser 

parser :: (String -> Maybe (a, String)) -> Parser a 
parser = Parser . StateT 

這部作品的原因是引擎蓋下StateT作爲實施：

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

如果你專注s到String，專門m到Maybe，您可以：

StateT String Maybe a ~ String -> Maybe (a, String) 

...這與您的類型相同。

StateT有自動爲你提供了以下情況：

instance Monad m => Functor  (StateT s m) 
instance Monad m => Applicative (StateT s m) 
instance Monad m => Monad  (StateT s m) 

instance Alternative m => Alternative (StateT s m) 

...我們可以專注於這些實例m到Maybe因爲Maybe同時實現Alternative和Monad：

instance Monad Maybe 

instance Alternative Maybe 

。 ..這意味着StateT s Maybe自動爲Functor,Applicative， Monad和Alternative，我們沒有做任何額外的工作。

該技巧的最後部分是GeneralizedNewtypeDeriving，它讓我們可以通過newtype包裝器提升類型類實例。由於我們的基礎StateT類型是Functor，Applicative，Monad和Alternative，我們可以自動加入解除通過我們的NEWTYPE所有四個類型的類實例：

... deriving (Functor, Applicative, Monad, Alternative) 

...編譯器會重新實現他們爲我們的NEWTYPE ，注意爲我們做所有的新型包裝和展開。

所以，如果你想弄清楚如何實現Applicative你的解析器，你可能想研究Applicative如何爲StateT實現，然後從該如何實現它的解析器類型推斷。