Migliore istanza applicativa per Parser (Haskell)

Question

Sto lavorando attraverso lo Brent Yorgey Haskell course e sto riscontrando problemi nella definizione di una buona istanza per Applicative. Un parser è definito come segue:

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

La funzione accetta una stringa, analizza una certa quantità di input e restituisce un forse tupla in cui il primo valore è il tipo del parser, e il resto è il resto unparsed della stringa. Ad esempio, questo è un parser per i numeri interi positivi:

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

L'assegnazione è quello di rendere un caso applicativo per Parser. Iniziamo con un'istanza Functor (che è relativamente straight-forward, credo):

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 

E poi ho provato la mia mano con applicativo:

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) 

... bleah. Quindi la mia domanda è: come posso rendere la mia istanza applicativa più pulita e meno difficile da leggere? Mi sembra che ci sia una risposta facile a questa domanda, ma non sono ancora riuscito a capire come funziona.

Answer 1

Suppongo che non ci sia ancora il numero Monad s nel corso. Il modo in cui si utilizza collapse e fmap indica che si sta essenzialmente reinventando Monad s per risolvere questo problema e in particolare l'istanza Monad Maybe. Infatti il ​​tuo collapse è lo stesso di join per questa monade. E infatti l'utilizzo di questo è un modo molto elegante per risolvere questo problema, ma forse un po '"barare" a questo punto. Quello che segue è la forma migliore ho potuto ottenere in durante l'uso delle funzioni:

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) 

Una volta che si arriva a Monad s corretta, si dovrebbe essere in grado di riscrivere questo con il (>>=) operatore ancora più succinta e/o do notazione .

Un'altra alternativa che è quasi altrettanto semplice, ma che non richiede di reinventare le monadi, consiste nell'usare la corrispondenza di pattern esplicita degli Maybe s. Quindi è possibile ottenere qualcosa del tipo:

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

Questo non è probabilmente quello che volete, ma ho voluto parlare di passaggio che c'è un modo molto succinto per implementare questa:

{-# 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 

Il motivo per cui funziona è che sotto il cofano StateT è implementato come :

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

Se siete specializzati s-String e specializzare m-Maybe, si ottiene:

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

... che è lo stesso del tipo.

StateT ha le seguenti casi previsti automaticamente per voi:

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) 

... e siamo in grado di specializzarsi m in quei casi per Maybe perché Maybe implementa sia Alternative e Monad:

instance Monad Maybe 

instance Alternative Maybe 

. .. quindi ciò significa che StateT s Maybe è automaticamente un Functor, Applicative, Monad e Alternative senza ulteriori interventi da parte nostra.

L'ultima parte del trucco è GeneralizedNewtypeDeriving, che ci consente di sollevare istanze di classe del tipo tramite un wrapper newtype. Dato che il nostro fondo StateT tipo è un Functor, Applicative, Monad, e Alternative, siamo in grado di sollevare automaticamente tutte le istanze di classe a quattro tipo attraverso il nostro Newtype aggiungendo:

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

... e il compilatore li reimplementare per il nostro newtype , avendo cura di fare tutto il nuovo tipo di confezione e scartoffia per noi.

Quindi, se si vuole capire come implementare Applicative per il parser, si consiglia di studiare come Applicative è implementato per StateT e poi dedurre da questa modalità di attuazione per il vostro tipo di parser.