[Haskell] Parser

[guylmaster]

Salve a tutti,
l'altro giorno sulla lezione dei parser mi sono letteralmente perso, forse anche per via delle slide della lezione molto stringate. Sapreste darmi qualche link o qualche dritta su cosa sono e come utilizzare i parser in Haskell ?

Certamente so cos'è a grossi linee un parser, ma semplicemente non riesco a capire cosa sono e a cosa servono queste funzioni parser in Haskell.

Ad esempio questo codice, sarebbe l'equivalente di un typdef del C? come lo dovrei interpretare?

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

Questa funzione qui, sopratutto il tipo, come va interpretata? Cioè qui "Parser" sembra più una funzione che un tipo. Ma allora Type a cosa serve? e la prima riga di qui sotto cosa fignifica? Oppure vuol significare di sostituire Char al posto di a nel tipo Parser? (e quindi sono una specie di java generics?)

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

Addirittura alla fine le combina le due scrivendo

Parser item "abc"

So di avere le idee un pò confuse ed il problema è proprio questo.

Vi ringrazio in anticipo,
guylmaster.

[marco.r]

Originariamente inviato da guylmaster

Salve a tutti,
l'altro giorno sulla lezione dei parser mi sono letteralmente perso, forse anche per via delle slide della lezione molto stringate. Sapreste darmi qualche link o qualche dritta su cosa sono e come utilizzare i parser in Haskell ?

Dipende da quale stai usando, comunque se usi Parsec prova a dare una occhiata qua:
http://book.realworldhaskell.org/read/using-parsec.html

Certamente so cos'è a grossi linee un parser, ma semplicemente non riesco a capire cosa sono e a cosa servono queste funzioni parser in Haskell.

Servono a leggere del testo ed interpretarne la struttura, ad esempio leggere un file .html e da li' ottenere la struttura ad albero del documento

Ad esempio questo codice, sarebbe l'equivalente di un typdef del C? come lo dovrei interpretare?

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

Questo dice che un Parser di valori di tipo "a" e' una qualsiasi funzione che prende una String come input e ritorna una lista di coppie (a,String)

Questa funzione qui, sopratutto il tipo, come va interpretata? Cioè qui "Parser" sembra più una funzione che un tipo. Ma allora Type a cosa serve?

type e' analoga ad una typedef del C. Dopo questa dichiarazione, usare "Parser a" oppure "String -> [(a,String)]" e' esattamente la stessa cosa.
Haskell e' un linguaggio funzionale in cui le funzioni sono "cittadini di serie A" al pari degli interi, delle stringe delle liste etc., per cui puoi usarli in tutti i contesti in cui puoi usare quest'ultimi.

e la prima riga di qui sotto cosa fignifica? Oppure vuol significare di sostituire Char al posto di a nel tipo Parser? (e quindi sono una specie di java generics?)

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

In haskell i tipi vengono sempre specificati con una maiuscola iniziale (Parser, Char, String etc.). Quando indichi un tipo, se utilizzi la notazione "Parser a" con un argomento minuscolo la dichiari parametrica (si' in un certo senso tipo i generics). Poi tu sostituisci la "variabile" a con un tipo concreto (e quindi Parser Char ad esempio).
Nel caso specifico tu dichiari che item prende come argomento un (Parser Char) ovvero non un qualsiasi Parser, ma solo quelli per i caratteri (ovvero: le funzioni String -> [(Char,String)]).

Parser item "abc"

Sei sicuro ? Non mi sembra una notazione corretta...

[Dan__88]

Se vuoi puoi dare un'occhiata al mio Thread
http://www.hwupgrade.it/forum/showthread.php?t=2409634

[guylmaster]

Originariamente inviato da Dan__88

Se vuoi puoi dare un'occhiata al mio Thread
http://www.hwupgrade.it/forum/showthread.php?t=2409634

Bè il tuo parser è ancora più complicato, così non è che abbia le idee più chiare. Non è che potresti chiarirmi i dubbi riproposti nel mio topic visto che sei un pò più esperto o magari indicarmi qualche link che potrebbe chiarirmeli?

[guylmaster]

Restringo la domanda, ovvero i dubbi:

- leggevo, nella definizione di parser il seguente codice:

> newtype Parser a              =  P (String -> [(a,String)])

Cioè Parser è un tipo? una specie di typedef del C? ovvero quando leggo Parser deve significare che c'è una certa funzione P che data una Stringa mi ritorni quella lista?

Quindi per questo ho bisogno di una funzione parse per applicare una funzione di parser ad una stringa:

parse :: Parser a -> String -> [(a,String)]
parse p inp = p inp

Ovvero parse va interpretata come una funzione che presi in input una funzione P del tipo (String -> [(a,String)]) e presa una stringa mi applica la funzione P alla stringa ritornandomi quindi la lista [(a,String)] ?
Quindi detto in poche parole noi abbiamo sia Parse che parser solo per rendere più leggibile il codice?

Ad esempio se prendiamo il parser item

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

Questo ci dice che è una funzione parser sostituisce nel "newtype" a con char e ci dice che preso in input una stringa ci restituisce una stringa del tipo [(char,String)]) ?
Però a questo punto mi sfugge perchè per eseguirla devo darla in input alla funzione parse. Probabilmente (anzi sicuramente) mi sfugge l'esatto significato di:

> newtype Parser a              =  P (String -> [(a,String)])

O più precisamente della parte a destra, ovvero:

P (String -> [(a,String)])

Per il resto il funzionamento su carta dei parser l'ho capito, quello che mi sfugge sostanzialmente è il significato che Hugs, quindi Haskell, da a Parser e a parse.

Forse è che mi sfugge cos'è una monade e nelle slide viene detto che Parser è una monade, qualcuno saprebbe darmi una definizione semplice della cosa?

[Dan__88]

Scusa prima di tutto mi diresti che libreria usi?
Io sto usando Parsec, che dovrebbe essere la più famosa per Haskell.

import Text.ParserCombinators.Parsec

[guylmaster]

Originariamente inviato da Dan__88

Scusa prima di tutto mi diresti che libreria usi?
Io sto usando Parsec, che dovrebbe essere la più famosa per Haskell.

import Text.ParserCombinators.Parsec

Io lo sto facendo in ambito universitario, quindi con liberie fatte ad hoc per lo studio, se vai su questo sito:

http://www.cs.nott.ac.uk/~gmh/book.html

la libreria è questa:
http://www.cs.nott.ac.uk/~gmh/parser.lhs

Ma ripeto sono poche righe di codice solo a scopo "di studio" però intanto così su due piedi mi sto perdendo.

[Dan__88]

Allora, intanto anch'io lo sto studiando in ambito accademico e sono molto MENO esperto di quanto pensi...

Originariamente inviato da guylmaster

> newtype Parser a              =  P (String -> [(a,String)])

Cioè Parser è un tipo? una specie di typedef del C? ovvero quando leggo Parser deve significare che c'è una certa funzione P che data una Stringa mi ritorni quella lista?

Si questo è una sorta di typedef del C.
Sinceramente non capisco a cosa serve esattamente..
Ma è diverso da quello che avevo scritto prima

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

Questo definisce un nuovo tipo per una funzione (lo capisci dalla freccetta), che prende in input una stringa e restituisce una LISTA di tuple (a, String).
Dove a è un parametro, ovvero può essere qualsiasi tipo.
Ad esempio

item :: Parser Char

Restituirà delle coppie (Char, String)

Comunque nelle librerie che sto usando io (e penso possa farlo anche tu) il tipo Parser è già definito, non capisco perchè a te lo facciano definire..

[Dan__88]

Originariamente inviato da guylmaster

Quindi per questo ho bisogno di una funzione parse per applicare una funzione di parser ad una stringa:

parse :: Parser a -> String -> [(a,String)]
parse p inp = p inp

Ovvero parse va interpretata come una funzione che presi in input una funzione P del tipo (String -> [(a,String)]) e presa una stringa mi applica la funzione P alla stringa ritornandomi quindi la lista [(a,String)] ?
Quindi detto in poche parole noi abbiamo sia Parse che parser solo per rendere più leggibile il codice?

No non credo sia una questione di leggibilità.
Penso sia necessaria, anche io ne uso una (trovata in rete)

run :: Show a => Parser a -> String -> IO ()
run p input
        = case (parse p "" input) of
            Left err -> do{ putStr "parse error at "
                          ; print err
                          }
            Right x  -> print x

In pratica esegue qualunque funzione di tipo Parser con una Stringa in input e stampa a video il risultato della parserizzazione (e gli eventuali errori)

[marco.r]

Originariamente inviato da guylmaster

> newtype Parser a              =  P (String -> [(a,String)])

Cioè Parser è un tipo? una specie di typedef del C? ovvero quando leggo Parser deve significare che c'è una certa funzione P che data una Stringa mi ritorni quella lista?

Si' Parser e' un tipo, in particolare un tipo parametrico
In rispetto al codice precedente pero' in questo caso e' stato usato newtype e non type, per cui non e' come una typedef (e infatti hai a destra P (String -> [(a,String)]),
Se hai un po' di esperienza di C e simili, consideralo qualcosa tipo una struct P con un singolo valore. In particolare questo vuol dire che le operazioni che prendono come argomento un (String -> [(A,String)]) non possono operare direttamente su un Parser a, a differenza di quanto accade col type di prima.

Quindi per questo ho bisogno di una funzione parse per applicare una funzione di parser ad una stringa:

parse :: Parser a -> String -> [(a,String)]
parse p inp = p inp

Questo codice non e' corretto, non dovrebbe compilarti se usi la newtype.
Funziona se usi la type. In quel caso Parser a non e' altro che un sinonimo di String ->[(a,String)] e parse e' solo scritta per leggibilita' (per uno poco abituato alla programmazione funzionale), in quanto se parse p inp e' uguale p inp tanto vale usare direttamente la seconda definizione.


Con la newtype invece quello che dovrebbe compilarti e' il codice seguente:

parse :: Parser a -> String -> [(a,String)]
parse (P p) inp = p inp

[/code]
Ovvero devi "tirare fuori" la funzione da Parser a con del pattern matching per poterla utilizzare.
Ma il fatto di definire una funzione parse per fare questo e' solo una scelta di comodo.

Ovvero parse va interpretata come una funzione che presi in input una funzione P del tipo (String -> [(a,String)]) e presa una stringa mi applica la funzione P alla stringa ritornandomi quindi la lista [(a,String)] ?
Quindi detto in poche parole noi abbiamo sia Parse che parser solo per rendere più leggibile il codice?

No, ricorda che avendo usato newtype Parser a non e' equivalente alla funzione, ma e' un nuovo tipo che contiene una funzione, per cui devi "estrarla" per usarla (come se tu avessi una struct in C con un puntatore a funzione tra i campi).

Ad esempio se prendiamo il parser item

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

Questo ci dice che è una funzione parser sostituisce nel "newtype" a con char e ci dice che preso in input una stringa ci restituisce una stringa del tipo [(char,String)]) ?

Anceh qui questo codice funziona se Parser a e' una typ,e non una newtype , per cui meglio se chiariamo di che codice stiamo parlando... :P
Se e' come penso allora item non e' altro che un particolare parser pensato per leggere caratteri (infatti legge un singolo carattere alla volta).

> newtype Parser a              =  P (String -> [(a,String)])

O più precisamente della parte a destra, ovvero:

P (String -> [(a,String)])

Per il resto il funzionamento su carta dei parser l'ho capito, quello che mi sfugge sostanzialmente è il significato che Hugs, quindi Haskell, da a Parser e a parse.

Allora parte della confusione e' dovuta che stai mescolando due codici diversi... riporta il codice al completo che poi riusciamo a discuterne meglio.
Quella riga dice che Parser a e' un nuovo tipo che e' costituito a sua volta da un singolo tipo preesistente (in questo caso una funzione). P e' un costruttore che serve per distinguerlo dal tipo contenuto: se f e' di tipo (String -> [(a,String)]), allora P f e' di tipo Parser a