Errore "Programmazione in Haskell" nella funzione sat

Question

Sono nel capitolo 8 della Programmazione di Graham Hutton in Haskell e sto copiando il codice e lo collaudo in GHC.

vedere le diapositive qui: http://www.cis.syr.edu/~sueo/cis352/chapter8.pdf in particolare slitta 15

Il codice in questione Ho copiato finora è:

type Parser a = String -> [(a, String)] 
pih_return :: a -> Parser a 
pih_return v = \inp -> [(v, inp)] 
failure :: Parser a 
failure = \inp -> [] 
item :: Parser Char 
item = \inp -> case inp of 
        [] -> [] 
     (x:xs) -> [(x,xs)] 
parse :: Parser a -> String -> [(a, String)] 
parse p inp = p inp 
sat :: (Char -> Bool) -> Parser Char 
sat p = do x <- item 
      if p x then pih_return x else failure 

ho cambiato il nome della funzione return dal libro al pih_return in modo che non sia in conflitto con la funzione Prelude return.

Gli errori si trovano nell'ultima funzione sat. L'ho copiato direttamente dal libro.

Come si può probabilmente vedere p è una funzione Char-Bool (ad esempio isDigit) e x è di tipo [(Char, String)], quindi questo è il primo errore.

Poi pih_return assume un valore v e restituisce [(v, inp)] dove inp è un String. Ciò causa un errore in sat perché lo v passato è x che non è un Char.

sono venuto su con questa soluzione, includendo esplicitamente inp in sat

E 'questo il modo migliore per risolvere il problema?

Answer 1

Il primo sat non può funzionare, Parser deve essere una monade Per utilizzare la notazione do. Per renderlo un'istanza monad, è necessario utilizzare newtype.

Non possiedo il libro, ma suppongo che l'autore volesse iniziare con un semplice tipo di parser e successivamente estenderlo a una monade completa e sospetto che abbiate confuso le definizioni delle versioni non monadiche con una della monade Parser (sat) e mancata la dichiarazione di istanza monad lungo la strada.

È disponibile il codice del capitolo on the author's web site in cui è stata definita un'istanza monad per Parser.

Se è necessario scrivere una funzione sat per il semplice Parser tipo preferirei farlo in lambda-stile (come item) ed evitare monadi del tutto (avete notato che l'originale sat s' do blocco era una monade Parser e la tua è una monade List?). E I penso che si sia verificato un errore nella versione sat: anziché pih_return (fst x) inp, penso che dovrebbe essere pih_return (fst x) (snd x).

Answer 2

Nelle diapositive manca l'implementazione della classe di caratteri Monad per il tipo Parser.

Con questa dichiarazione, la notazione do è corretta; x <- item esegue effettivamente lo unwrapping corretto da [(Char, String)] a (Char, String).

io non riesco a ottenere questa definizione senza compilare per vedere l'errore, ma è un inizio:

instance Monad (Parser a) where 
    return x = pih_return x 
    -- (>>=) :: Parser a -> (a -> Parser b) -> Parser b 
    p >>= f = \inp -> case p inf of 
         [] -> [] 
         (x:xs) -> (f x) xs -- this line is probably wrong 
    fail message = [] -- message is ignored 

Answer 3

Non è possibile utilizzare la notazione do senza una monade, e non è possibile effettuare una istanza monad a meno che non si usi data o newtype e non sia possibile utilizzare data o newtype a meno che non si presenti un costruttore di valore fastidioso. Indubbiamente il costruttore di valore è stato omesso solo perché è fastidioso.

Nell'esempio seguente è possibile vedere che ho utilizzato newtype e ho introdotto il fastidioso costruttore di valori Parser. Questo è ciò che rende la dichiarazione instance funzionante e, a questo punto, è possibile utilizzare non solo do -notation ma anche lo standard monadico return e fail.

Questo codice viene compilato senza errori o avvisi:

module P 
where 

newtype Parser a = Parser (String -> [(a, String)]) 
instance Monad Parser where 
    return a = Parser $ \inp -> [(a, inp)] 
    fail _ = Parser $ \_ -> [] 
    Parser f >>= k = Parser $ \inp -> 
    [(b, inp'') | (a, inp') <- f inp, let Parser g = k a, (b, inp'') <- g inp'] 

item :: Parser Char 
item = Parser $ \inp -> case inp of 
          [] -> [] 
          (x:xs) -> [(x,xs)] 
parse :: Parser a -> String -> [(a, String)] 
parse (Parser p) inp = p inp 
sat :: (Char -> Bool) -> Parser Char 
sat p = do x <- item 
      if p x then return x else fail "predicate not satisfied" 

Answer 4

sto leggendo lo stesso libro e arrivato lo stesso problema quando si cerca di fare gli esercizi. Sono tornato dall'uso della notazione "fai ..." a >> =. Per chiunque fosse interessato ho inserito il mio codice fino all'utilizzo della funzione nat. Ho anteposto tutte le mie funzioni a un e modificato >> = a >>> = per evitare conflitti di nome con preludio.

type AParser a = String -> [(a, String)] 
areturn :: a -> AParser a 
areturn v = \inp -> [(v, inp)] 
afailure :: AParser a 
afailure = \inp -> [] 
aitem :: AParser Char 
aitem = \inp -> case inp of 
        [] -> [] 
        (x:xs) -> [(x, xs)] 
aparse :: AParser a -> String -> [(a, String)] 
aparse p inp = p inp 
(>>>=) :: AParser a -> (a -> AParser b) -> AParser b 
p >>>= f = \inp -> case aparse p inp of 
        [] -> [] 
        [(v, out)] -> aparse (f v) out 
(+++) :: AParser a -> AParser a -> AParser a 
p +++ q = \inp -> case aparse p inp of 
        [] -> aparse q inp 
        [(v, out)] -> [(v, out)] 
asat :: (Char -> Bool) -> AParser Char 
asat p = aitem >>>= (\x -> if p x then areturn x else afailure) 
adigit :: AParser Char 
adigit = asat isDigit 
amany :: AParser a -> AParser [a] 
amany p = amany1 p +++ areturn [] 
amany1 :: AParser a -> AParser [a] 
amany1 p = p >>>= (\v -> (amany p) >>>= (\vs -> areturn (v:vs))) 
anat :: AParser Int 
anat = amany1 adigit >>>= (\xs -> areturn (read xs))