Pages: [1] 2   Go Down
Print
Author Topic: Possibile soluzione all'esercizio haskell "Definire il Pattern Matching di PICT"  (Read 1913 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
rondey
Matricola
*
Offline Offline

Posts: 74


« on: 18-04-2016, 08:35:24 »

Sono ben consapevole che la funzione CheckPatts sia tutt'altro che perfetta nei casi di pattern formati da liste di liste, purtroppo però non sono riuscito a trovare una soluzione perfettamente corretta....
Per tutto il resto, mi sembra corretto.
Code:
data Value = ValNum Int | ValString [Char] | ValBool Bool | ValName Char
    deriving (Show, Eq)

data Values = ValList Value Values | ValListList Values Values | ValEmpty
    deriving (Show, Eq)

data PicValue = NewValue Value | NewValues Values
    deriving (Show)

data Pattern = PatVar Char
    deriving (Show,Eq)

data Patterns =  PatList Pattern Patterns | PatListList Patterns Patterns | PatEmpty
    deriving (Show,Eq)

data PicPatterns = NewPattern Pattern | NewPatterns Patterns
    deriving (Show)

data Bind = BindOtO Pattern Value | BindMtO Pattern Values | NotValidBind
     deriving (Show, Eq)

data Binds = BinsEmpty | Binds Bind Binds | BindsBinds Binds Binds | NotValidBinds
     deriving (Show, Eq)

data PicBinding = NewBind Bind | NewBinds Binds | NotValid
    deriving (Show, Eq)
   
v1 = ValNum 25

v2 = ValString "Ciao"
   
listV = ValList v1 (ValList v2 ValEmpty)

pattern = PatVar 'l'

p1 = PatVar 'a'

p2 = PatVar 'b'

p3 = PatVar 'b'

p4 = PatVar 'd'

listP = PatList p1 (PatList p2 PatEmpty)
listP2 = PatList (PatVar 'c') (PatList p4 PatEmpty)

--Effettuo un controllo sui caratteri dei pattern, assicurandomi che il pattern formato da una lista non
--presenti più volte uno stesso carattere
checkPatts PatEmpty = True
checkPatts (PatList p ps)
    | (checkPatts ps) && (scrollPatt p ps) = True
    | otherwise = False
checkPatts (PatListList (PatList p ps) pss)
    | (checkPatts ps) && (checkPatts pss) && (scrollPatt p ps) && (scrollPatt p pss) = True
    | otherwise = False
checkPatts (PatListList (PatListList ps pss) psss)
     | (checkPatts ps) && (checkPatts pss) && (checkPatts psss) = True
     | otherwise = False

--Confronto il singolo carattere p con tutti i restanti caratteri della lista
scrollPatt p PatEmpty = True
scrollPatt (PatVar p) (PatList x xs)
    | (scrollPatt (PatVar p) xs) && (((PatVar p)/=x)||(p=='_')) = True
    | otherwise = False
scrollPatt p (PatListList xs xss)
    | (scrollPatt p xs) && (scrollPatt p xss) = True
    | otherwise = False
   

     
--esempio di lista di pattern che non può superare il controllo: p2 e p3 hanno lo stesso carattere
listPwrong = PatList p1 (PatList p2 (PatList p3 (PatList p4 PatEmpty)))

--Operazione di binding
picBind v (NewPattern p) = NewBind (bind v p)
picBind (NewValue v) (NewPatterns p) = NotValid
picBind (NewValues vs) (NewPatterns ps)
    | (checkPatts ps) && (b /= NotValidBinds) = NewBinds b
    | otherwise = NotValid
    where b = binds vs ps

bind (NewValue v) p = BindOtO p v
bind (NewValues vs) p = BindMtO p vs

binds ValEmpty PatEmpty = BinsEmpty
binds (ValList v vs) (PatList p ps)
     | (b/=NotValidBinds) = Binds ( bind (NewValue v) p ) ( b )
     | otherwise = NotValidBinds
     where b = binds vs ps
binds (ValListList vs vss) (PatList p ps) = NotValidBinds
binds (ValListList vs vss) (PatListList ps pss) =
    BindsBinds (binds vs ps) (binds vss pss)
     
listB1 = picBind (NewValues listV) (NewPatterns listP)
listB2 = picBind (NewValues listV) (NewPattern p1)

listB3 = picBind (NewValues (ValListList listV (ValListList listV (ValListList listV ValEmpty)))) (NewPatterns (PatListList listP (PatListList listP2 (PatListList listP2 PatEmpty))))
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.800



WWW
« Reply #1 on: 18-04-2016, 09:18:16 »

Il costruttore
ValList
chiamiamolo
Tuple

ValEmpty
chiamiamolo
EmptyTuple

E chiamerei
direttamente
PicValue
quello che chiami Value.

proverei poi a vedere se non sia meglio definire
Pattern
come
data Pattern = Pattern PictValue

I Bind sono funzioni, definiamole come tali
Prova a fare
data Binding = Binding   Names -> PictValues

definendo Names


« Last Edit: 18-04-2016, 09:23:55 by Franco Barbanera » Logged
Ocelot92
Apprendista Forumista
**
Offline Offline

Posts: 301



« Reply #2 on: 18-04-2016, 22:24:58 »

proverei poi a vedere se non sia meglio definire
Pattern
come
data Pattern = Pattern PictValue

Penso pure io dato che abbiamo visto che sono la stessa cosa, cambia soltanto la semantica dei nomi che per i valori rappresentano canali mentre per i pattern dei buchi/variabili.

UPDATE:
Code:
-- Exercise:
-- - define in haskell the data type of pict values
-- - define the data type of patterns
-- - define the data types of bindings
-- - define the pattern matching operation

data PictValue = IntVal Int | StrVal [Char] | NameVal Char | PattTuple [Pattern]

data Pattern = NewPattern PictValue
Non sto trovando una definizione di bind da cui modellare il tipo in Haskell.
« Last Edit: 19-04-2016, 08:11:53 by Ocelot92 » Logged

I'm happy to tell you all that...
((λf.λx.f(f(x))) (λy.y^2)) (5)  = 5^4

"Si ma dillo che bisogna cliccare APPLY per crearle le partizioni…" - cit. Utente dopo aver seguito un How-To... .-.
rondey
Matricola
*
Offline Offline

Posts: 74


« Reply #3 on: 19-04-2016, 16:07:25 »

Code:
data PicValue = ValNum Int | ValString [Char] | ValBool Bool | ValName Char | Tuple [PicValue]
    deriving (Show, Eq)

data Pattern = Pattern PicValue
    deriving (Show,Eq)

data Binding = Binding Name PicValue
    deriving (Show, Eq)
   
data Name = Name Char | TupleName [Name]
    deriving (Show,Eq)
   
v1 = ValNum 25

v2 = ValString "Ciao"
   
tuplaV = Tuple [v1, v2]

pattern = ValString ""

n1 = Name 'a'

n2 = Name 'b'

n3 = Name 'b'

n4 = Name 'd'

--listP2 = Pattern (PatVar 'c') (PatList p4 PatEmpty)


checkMatching (Name n) v = True

checkMatching (TupleName ns) (ValNum i) = False
checkMatching (TupleName ns) (ValString cs) = False
checkMatching (TupleName ns) (ValBool b) = False
checkMatching (TupleName ns) (ValName c) = False

checkMatching (TupleName []) (Tuple []) = True
checkMatching (TupleName ns) (Tuple []) = False
checkMatching (TupleName []) (Tuple vs) = False
checkMatching (TupleName (n:ns)) (Tuple (v:vs)) = (checkMatching n v) && (checkMatching (TupleName ns) (Tuple vs))


patternMatching (Binding n v)
     | (checkMatching n v) = Pattern (matching n v)
     | otherwise = Pattern (Tuple [])
     
matching (Name n) v = v

matching (TupleName []) (Tuple []) = Tuple []
matching (TupleName (n:ns)) (Tuple (v:vs)) =
    (matching n v) : (matching ns vs)
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.800



WWW
« Reply #4 on: 19-04-2016, 18:17:51 »

Quote
data Name = Name Char | TupleName [Name]
    deriving (Show,Eq)

Non credo serva TupleName

Il tipo dei nomi lo definisci con
data Name = Name Char    (meglio Name String, altrimenti hai solo un numero di nomi pari al numero
                                             finito dei caratteri...)

E poi nella definizione di PictValue metti

...|  ValName Name ...
al posto di
...|  ValName Char ...
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.800



WWW
« Reply #5 on: 19-04-2016, 18:24:50 »

data Pattern = Pattern PicValue
    deriving (Show,Eq)

Forse pero' conviene definire Pattern esattamente come Value
usando costruttori come PattNum, PattName ecc.
Credo aumenti di molto la laggibilita'.

L'uso dei TupleName nella funzione matching e' per me un mistero....
Perche' usi TupleName?

Salutoni
FB
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.800



WWW
« Reply #6 on: 19-04-2016, 18:33:07 »

Per definire la funzione di matching suggerirei l'uso del case di Haskell, nel seguente modo

matching patt value = case (patt,value) of
                                           
                                            (PattName, v) ->   ecc.
                                            (PattNum n, ValNum m ) ->  ecc.
                                             ecc.
                                             ( _,_)   _>  questo e' il caso in cui nessuna coppia vada bene


Logged
rondey
Matricola
*
Offline Offline

Posts: 74


« Reply #7 on: 21-04-2016, 14:30:35 »

L'uso dei TupleName nella funzione matching e' per me un mistero....
Perche' usi TupleName?

Salutoni
FB

Purtroppo mi confondo, la definizione (scarna) di Pattern matching presente nel pdf mi manda in confusione con come lo ha spiegato Lei e come nel Pict agisco effettivamente. Mi spiego:

Code:
run ( new ch: ^[String String]
      ( ch!["Hello" "world"]
      | ch?[b c] = ( print!b
                     | print!c
    ) )              )

Io qui non sto dicendo che b sarà di tipo PattString, in realtà io dico che il canale deve accettare una tupla composta di due elementi String. Sarà poi PICT a dire "ok, visto che nel canale ch mi aspetto due String, allora b e c devono essere entrambi di tipo String". b e c li vedevo di conseguenza come dei semplici caratteri, dei semplici nomi che rappresentano i corrispettivi pattern.
Comunque, ho riformulato la definizione in questo modo
Code:
data PicValue = ValNum Int | ValString [Char] | ValBool Bool | ValName Name | Tuple [PicValue]
    deriving (Show, Eq)

data Pattern = PattNum Int | PattString [Char] | PattBool Bool | PattName Name | PattTuple [Pattern]
    deriving (Show, Eq)

data Binding = Binding Name Pattern PicValue
    deriving (Show, Eq)
   
data Name = Name [Char]
    deriving (Show,Eq)
   
tuplaP=PattTuple [PattTuple [PattNum 0, PattNum 0], PattNum 0]
tuplaV=Tuple [Tuple [ValNum 35, ValNum 50], ValNum 1]

patternMatching (Binding n p v) = matching p v
     
matching patt value = case (patt,value) of
    (PattNum p, ValNum v ) ->  PattNum v
    (PattString p, ValString v ) ->  PattString v
    (PattBool p, ValBool v) ->   PattBool v
    (PattName p, ValName v) ->   PattName v
    (PattTuple [], Tuple []) ->   PattTuple []
    (PattTuple (p:ps), Tuple (v:vs)) -> PattTuple  ((matching p v):ls)
        where PattTuple ls= matching (PattTuple ps) (Tuple vs)
    ( _, _)   -> PattTuple []

binding=Binding (Name "c") tuplaP tuplaV
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.800



WWW
« Reply #8 on: 22-04-2016, 09:40:43 »

Quello in fondo alla pagina e' quello che abbiamo fatto ieri a lezione.
Dategli una sistemata.
E fornite una formulazione alternativa (e piu' elegante)
in cui il tipo Substitution e' definito come

Code:
type Substitution = Name -> PicValue

C'e' poi da fare il programma Erlang che controlla se due tipi PICT sono in
relazione di sottotipo.

E per finire, fornire dei processi PICT che facciano capire il senso della relazione
di sottotipo su tipi input e su tipi output.

Salutoni
FB     

Code:
data PicValue = ValNum Int | ValString [Char] | ValBool Bool | ValName Name | Tuple [PicValue]
    deriving (Show, Eq)


data Pattern = PattNum Int | PattString [Char] | PattBool Bool | PattName Name | PattTuple [Pattern]
    deriving (Show, Eq)




data Substitution = MkSubstitution [(Name,PicValue)]

concatSubstitution (MkSubstitution ls1) (MkSubstitution ls2) =

                      (MkSubstitution   ls1++ls2)
         

--(definizione alternativa) type Substitution = Name -> PicValue
   

data Name = Name [Char]
    deriving (Show,Eq)
   
mytuplaP=PattTuple [PattTuple [PattNum 0, PattNum 0], PattNum 0]

mytuplaV=Tuple [Tuple [ValNum 35, ValNum 50], ValNum 1]


matching :: Pattern -> PicValue -> (Bool,Substitution)
     
matching patt value =

  case (patt,value) of

    (PattNum n, ValNum m ) ->  ((n==m),MkSubstitution [])

    (PattString s1, ValString s2 ) ->  ((s1==s2),MkSubstitution [])

    (PattBool b1, ValBool b2) ->   ((b1==b2), MkSubstitution[])

    (PattName a, v) ->   (True, (MkSubstitution [((PattName a),v)])

    (PattTuple [], Tuple []) ->   (True, (MkSubstitution [])
   
    (PattTuple [], v)        ->   (False, (MkSubstitution [])

    (p, Tuple [])            ->   (False, (MkSubstitution [])

    (PattTuple (p:ps), Tuple (v:vs)) | b = (b0, MkSubstitution (concatSubstitution s0 s))
                                            where (b0,s0) =  (matching p v)

                                     | otherwise = (False,Mksubstitution [])
             
                          where  (b,s) = (matching ps vs)
                                 
Logged
rondey
Matricola
*
Offline Offline

Posts: 74


« Reply #9 on: 25-04-2016, 16:08:31 »

Versione funzionante
Code:
data PicValue = ValNum Int | ValString [Char] | ValBool Bool | ValName Name | Tuple [PicValue]
    deriving (Show, Eq)

data Pattern = PattNum Int | PattString [Char] | PattBool Bool | PattName Name | PattTuple [Pattern]
    deriving (Show, Eq)

 
data Substitution = MkSubstitution [(Name, PicValue)]
    deriving (Show)

concatSubstitution (MkSubstitution ls1) (MkSubstitution ls2) = MkSubstitution (ls1++ls2)
concatTuple (Tuple ls1) (Tuple ls2) = Tuple (ls1++ls2)
concatTuple v (Tuple ls) = Tuple (v:ls)
concatTuple v1 v2 = Tuple [v1, v2]

   
data Name = Name [Char]
    deriving (Show,Eq)
   
mytuplaP=PattTuple [PattTuple [PattName (Name "x"), PattName (Name "y")], PattName (Name "z")]
mytuplaV=Tuple     [Tuple     [ValNum 35          , ValNum 50          ], ValNum 1]

matching :: Pattern -> PicValue ->(Bool, Substitution)
     
matching patt value =
    case (patt,value) of
       
        (PattNum n, ValNum m ) ->  ((n == m), (MkSubstitution []))
       
        (PattString s1, ValString s2 ) ->  ((s1==s2), (MkSubstitution []))
       
        (PattBool b1, ValBool b2) ->   ((b1==b2), (MkSubstitution []))
       
        (PattName a, value) ->   (True, (MkSubstitution [(a, value)]))
       
        (PattTuple [], Tuple []) ->   (True, (MkSubstitution []))
       
        (PattTuple [], value) ->    (False, (MkSubstitution []))
       
        (PattTuple (p:ps), Tuple (v:vs)) | b -> (b0, (concatSubstitution s0 s))
                                         | otherwise -> (False, (MkSubstitution []))
                                            where (b0,s0) =  (matching p v)
                                                  (b,s) = (matching (PattTuple ps) (Tuple vs))
        (patt, value) -> (False, (MkSubstitution []))
« Last Edit: 26-04-2016, 12:21:59 by rondey » Logged
Ocelot92
Apprendista Forumista
**
Offline Offline

Posts: 301



« Reply #10 on: 25-04-2016, 19:51:11 »

Dubbio:
Code:
data Substitution = MkSubstitution [(Name, PicValue)]
    deriving (Show)

Non dovrebbe essere: MkSubstitution [(Pattern, PicValue)] ?

Nei case quando facciamo "PattNum n" alla fine stiamo usando il costruttore di un Pattern.
Logged

I'm happy to tell you all that...
((λf.λx.f(f(x))) (λy.y^2)) (5)  = 5^4

"Si ma dillo che bisogna cliccare APPLY per crearle le partizioni…" - cit. Utente dopo aver seguito un How-To... .-.
rondey
Matricola
*
Offline Offline

Posts: 74


« Reply #11 on: 25-04-2016, 22:00:26 »

La substitution consiste in una coppia dove come primo elemento c'è il nome della variabile e come secondo il valore da associare alla variabile. La funzione matching si occupa proprio di creare tali substitution utilizzando come input il pattern dal quale ricavare come output eventualmente il nome della variabile e il valore.
Logged
Ocelot92
Apprendista Forumista
**
Offline Offline

Posts: 301



« Reply #12 on: 25-04-2016, 23:10:27 »

La substitution consiste in una coppia dove come primo elemento c'è il nome della variabile e come secondo il valore da associare alla variabile. La funzione matching si occupa proprio di creare tali substitution utilizzando come input il pattern dal quale ricavare come output eventualmente il nome della variabile e il valore.
Ok, dubbio chiarito. Grazie.
Logged

I'm happy to tell you all that...
((λf.λx.f(f(x))) (λy.y^2)) (5)  = 5^4

"Si ma dillo che bisogna cliccare APPLY per crearle le partizioni…" - cit. Utente dopo aver seguito un How-To... .-.
Ocelot92
Apprendista Forumista
**
Offline Offline

Posts: 301



« Reply #13 on: 26-04-2016, 08:05:08 »

Versione funzionante
Code:


     data PicValue = ValNum Int | ValString [Char] | ValBool Bool | ValName Name | Tuple [PicValue]
    deriving (Show, Eq)

data Pattern = PattNum Int | PattString [Char] | PattBool Bool | PattName Name | PattTuple [Pattern]
    deriving (Show, Eq)

  
data Substitution = MkSubstitution [(Name, PicValue)]
    deriving (Show)

concatSubstitution (MkSubstitution ls1) (MkSubstitution ls2) = MkSubstitution (ls1++ls2)

--(definizione alternativa)type Substitution = Name -> PicValue
    
data Name = Name [Char]
    deriving (Show,Eq)
    
MytuplaP=PattTuple [PattTuple [PattName (Name "x"), PattName (Name "y")], PattName (Name "z")]
MytuplaV=Tuple     [Tuple     [ValNum 35          , ValNum 50          ], ValNum 1]



matching :: Pattern -> PicValue ->(Bool, Substitution)
    
matching patt value =
    case (patt,value) of
        
        (PattNum n, ValNum m ) ->  ((n == m), (MkSubstitution []))
        
        (PattString s1, ValString s2 ) ->  ((s1==s2), (MkSubstitution []))
        
        (PattBool b1, ValBool b2) ->   ((b1==b2), (MkSubstitution []))
        
        (PattName a, value) ->   (True, (MkSubstitution [(a, value)]))
        
        (PattTuple [], Tuple []) ->   (True, (MkSubstitution []))
        
        (PattTuple [], value) ->    (False, (MkSubstitution []))
        
        (PattTuple (p:ps), Tuple (v:vs)) | b -> (b0, (concatSubstitution s0 s))
                                         | otherwise -> (False, (MkSubstitution []))
                                            where (b0,s0) =  (matching p v)
                                                  (b,s) = (matching (PattTuple ps) (Tuple vs))
        (patt, value) -> (False, (MkSubstitution []))

                                
Mentre scrivevo la mia versione mi era venuto un dubbio riguardo l'algoritmo fatto a lezione e volevo provarlo sulla tua versione. Tuttavia facendo copia incolla da un paio di errori (dava errori sui deriving, è bastato indentarli però). Forse sarebbe meglio passare al servizio pastebin?
Inoltre GHCi si lamenta sulle variabili che ti sei creato per test, devono iniziare per minuscole. Hugs non ti da problemi?

PS: l'algoritmo funziona, il caso particolare a cui pensavo è previsto.
« Last Edit: 26-04-2016, 08:11:12 by Ocelot92 » Logged

I'm happy to tell you all that...
((λf.λx.f(f(x))) (λy.y^2)) (5)  = 5^4

"Si ma dillo che bisogna cliccare APPLY per crearle le partizioni…" - cit. Utente dopo aver seguito un How-To... .-.
rondey
Matricola
*
Offline Offline

Posts: 74


« Reply #14 on: 26-04-2016, 09:15:42 »

Più che altro, avrei dovuto utilizzare il pc, non il cellulare per pubblicare il codice cry


Aggiornato tramite Computer il codice haskell
« Last Edit: 26-04-2016, 12:22:36 by rondey » Logged
Pages: [1] 2   Go Up
Print
Jump to: