Perché sto ottenendo un errore di tipo in questa sequenza di parser (lezione 8 di Erik Meijer)?

Question

Sono in procinto di guardare il Fondamenti di programmazione funzionale serie di conferenze di Erik Meijer (con diapositive di Graham Hutton).

In lecture 8 (on functional parsers), dopo aver definito il tipo Parser a, introducendo alcune primitive di analisi (tra cui item e return, che ho chiamato return'), Erik dà un simple example di come i suoi parser possono essere combinati in una sequenza, utilizzando la sintassi fare:

type Parser a = String -> [(a,String)] 

item :: Parser Char             
item = \inp -> case inp of             
       []  -> []            
       (x:xs) -> [(x,xs)] 

return' :: a -> Parser a             
return' v = \inp -> [(v,inp)] 

p :: Parser (Char,Char) 
p = do x <- item 
     item 
     y <- item 
     return' (x,y) 

Tuttavia, quando provo a caricare questo GHCi, ottengo il seguente errore di tipo, che non mi aspettavo e non capisco:

Couldn't match type ‘[(Char, String)]’ with ‘Char’ 
Expected type: String -> [((Char, Char), String)] 
    Actual type: Parser ([(Char, String)], [(Char, String)]) 
In a stmt of a 'do' block: return' (x, y) 
In the expression: 
    do { x <- item; 
     item; 
     y <- item; 
     return' (x, y) } 
Failed, modules loaded: none. 

Cosa sto sbagliando?

Answer 1

Il problema è che la notazione nella definizione di p non utilizza la monade che si desidera venga utilizzata.

Potrei sbagliarmi, ma sembra che p stia utilizzando una versione di Reader monad.

Se si utilizza questa definizione si vedrà che x e y non sono Char valori ma hanno tipo [(Char,String)]:

import Debug.Trace 

p :: Parser (Char,Char) 
p = do x <- item 
     y <- item 
     let foo = trace ("x = " ++ show x) 'a' 
      bar = trace ("y = " ++ show y) 'b' 
     return' (foo,bar) 

test = p "qwe" 

Se si desidera utilizzare la notazione do, si dovrebbe creare una dichiarazione newtype o data per Parser modo è possibile definire come funziona l'operatore bind (>> =), ad esempio:

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

instance Monad Parser where 
    return = Parser . return' 
    (>>=) = ... 

Ecco un buon post sul blog su come definire un'istanza monad parser usando newtype: (link)

Answer 2

Questo messaggio di errore è un po 'di confusione perché GHC ha decompresso il tuo tipo Parser nella sua definizione di String -> [(a, String)]. Se si disfa questa trasformazione, che sarà iniziare a fare un po 'più senso:

Expected type: Parser (Char, Char) 
    Actual type: Parser ([(Char, String)], [(Char, String)]) 

ora è di iniziare a fare un po' più senso. Quello che sembra è che hai preso il risultato di due chiamate a Parser Char (ovvero [(Char, String)]) e le hai usate come se fossero normali Char s. L'errore si verifica in corrispondenza della linea 15, che è la vostra chiamata a return':

return' (x, y) 

Questo ci dice che x e y sono i due risultati problematici.

Il blocco do che si sta utilizzando è l'istanza monad per funzioni del tipo String -> b; ciò che fa è combinarli in una più ampia funzione di String -> b stringendo l'input (String) attraverso tutte le funzioni. Una riga come x <- item consente di ottenere l'elementodalla funzione String -> b mantenendo tutti gli impianti idraulici per passare attraverso l'argomento String. Purtroppo, item è un Parser Char, il che significa che lo b è in realtà un [(Char, String)] e non solo uno Char.

Questa struttura di reso aggiuntiva è necessaria per analizzare correttamente. Il String rappresenta il resto dell'ingresso che non è stato consumato per analizzare lo Char (o qualsiasi cosa si stia analizzando) e l'intera cosa è una lista perché ci possono essere molteplici modi per analizzare validamente parte dell'input che tutti devono essere maneggiato.

Per fare in modo che questo lavoro, devi avere un modo per prendersi cura di questa struttura in più. Tuttavia, poiché non ho seguito il corso o guardato la lezione, non so cosa sia. Potresti definire la tua istanza monad invece di fare affidamento sull'istanza integrata per le funzioni, ma potresti non aver ottenuto abbastanza nella classe per farlo da solo, oppure Meijer potrebbe utilizzare una libreria non standard per evitare questo problema, nel qual caso è necessario assicurarsi che il proprio setup corrisponda a ciò che la classe si aspetta.