[CAML] Aiuto su automi

[Marco89__1]

Salve a tutti!

Avrei bisogno di una mano con un esercizio in CAML, in pratica usando gli automi dovrei verificare se date 2 lettere in input e una lista di parole , il programma mi restituisca TRUE se esse sono presenti almeno una volta nelle parole altrimenti FALSE se non sono presenti. Devo usare la funzione member?

Grazie,

Marco

[hamming_burst]

Ciao,

"Marco89__":usando gli automi

sai creare nuovi tipi?

"Marco89__":dovrei verificare se date 2 lettere in input e una lista di parole , il programma mi restituisca TRUE se esse sono presenti almeno una volta nelle parole altrimenti FALSE se non sono presenti. Devo usare la funzione member?

cosa non riesci di preciso, quale è il tuo dubbio nella risoluzione?

[Marco89__1]

Si, so creare nuovi tipi. Il problema è la ricerca degli elementi con la funzione member..se devo cercare due elementi la devo richiamare due volte nella mia funzione?

[apatriarca]

Non sono certo di aver capito quale sia il tuo problema. Potresti fornirci maggiori informazioni sui tuoi dubbi e forse un po' di codice mostrando i tuoi tentativi?

[Marco89__1]

type 'a elenco = parolavuota | parola of 'a list * 'a elenco;;

#let rec member x l = match l with
[] -> false
| y::ys when x=y -> true
|y::ys when x<>y -> member x ys;;

let rec check c x p =
	let rec member l y = match l with
		[] -> false |
		z :: zs -> if y=z then member zs y else false
	in 
	let rec member l t = match l with
		[] -> false |
		r :: rs -> if t=r then member rs t else false
	in 
		match c with
			parolavuota -> false 	|
		elenco(l,c1)-> if member l x & member l p then true else false;;

-------------------

Diciamo che sto andando a tentativi!

[hamming_burst]

Guarda che devi utilizzare gli automi.
Specializzare poi in algorimo che in input avrà una lista, ma come stuttura di analisi utilizza l'automa con stati e transizioni.

Quindi, prima di tutto formalizza il tipo automa.

[Marco89__1]

Ah dovrei usare un automa deterministico..cambia qualcosa nella struttura? purtroppo non riesco a trovare il manuale di Caml online quindi mi risulta tutto più difficile.

[apatriarca]

Non sono un esperto di OCaml, ma credo che gli automi siano da usare a livello teorico e non tanto nell'implementazione. Di fatto un automa a stati finiti è qualcosa di molto astratto ed è possibile implementarlo in modi anche molto diversi in OCaml (o in qualsiasi altro linguaggi di programmazione).

[Marco89__1]

si dovrebbero essere proprio a livello teorico..almeno da quel che ho capito

[hamming_burst]

Visto che mi hai inviato il testo esatto dell'esercizio continuiamo in questo thread.

"Marco89__ ":Scrivere un programma in CAML che verifichi se date 2 lettere in input e una lista di parole , il programma mi restituisca TRUE se esse sono presenti almeno una volta nelle parole altrimenti FALSE se non sono presenti. (implementando gli automi deterministici).

come ha scritto apatriarca a buon ragione ed accennato io in PM, gli automi (modello generale) posson esser solo impliciti nella stesura di un modello, algoritmo, od altro (si pensi agli interpreti ed ai parser) nella maggior parte dei casi. Ma questo essendo un esercizio didattico molto basilare, bisogna implementarli come da testo...

La stesura non è molto complicata, basta andare per gradi, prima penso sia meglio scrivere le due righe di codice che risolvono il problema esplicitamente (liste) così comprendi il ragionamento mentale ci sta dietro ai vari passaggi, poi traduciamo il tutto con gli automi.

Nel tuo codice che hai proposto ti crei il tipo coppia (lista,elenco), ti crei delle funzioni specializzate su questo tipo...
un modo davvero non ottimale, perchè ti crei in pratica funzioni e tipi che esistono e sono stati già scritti da qualcun'altro.

Il tipo (almeno in O'Caml) non è interpretabile:

type 'a elenco = parolavuota | parola of 'a list * 'a elenco;;

perchè è convenzione utilizzare nome maiuscoli per i costruttori:

type 'a elenco = Parolavuota | Parola of 'a list * 'a elenco;;

#let rec member x l = match l with
[] -> false
| y::ys when x=y -> true
|y::ys when x<>y -> member x ys;;

l'utilizzo massiccio delle guardie non è proprio buona programmazione nei linguaggi funzionali. La guardi la sia usa in casi particolari per singole eccezzioni uniche, non la si deve usare per la condizione di uscita principale ma solo secondaria. Penso stavi ragionando per iterazione, ma non è un if od un while!!
Non mi dilungo sul tuo codice, troppo complicato per un esercizio di due righe che alla fine non risolverebbe il problema degli automi, ma solo quello delle liste. Quindi ricominciamo:

"Marco89__ ":
Scrivere un programma in CAML che verifichi se date 2 lettere in input e una lista di parole

come spero tu sappia CAML ha la tipizzazione forte, quindi ogni elemento od oggetto ha un tipo ben definito (tranne le funzioni parziali od i tipi astratti).
Interpretiamo l'input come due caratteri ed una lista di stringhe quindi:

char -> char -> string list

"Marco89__ ":il programma mi restituisca TRUE se esse sono presenti almeno una volta nelle parole altrimenti FALSE se non sono presenti.

il tipo di ritorno essendo true o false sarà un booleano quindi:

char -> char -> string list -> bool = <fun>

Le funzioni in gioco saranno su tipi:
- list
- strig
- char

La condizione di uscita è un exists, cioè se almeno una volta in tutta la lista entrambi i caratteri sono contenuti nella stessa parola allora tornerà true. Tale condizione può essere interpretata come un AND ed un'iterazione su ogni singola stringa una per ogni carattere. Se in una ricorsione c'è mismatch il programma continuerà fino alla fine della lista e tornerà false.

let string_doubleconf c1 c2 string = (String.contains string c1) && (String.contains string c2);;

# val string_doubleconf : char -> char -> string -> bool = <fun>

utilizziamo la funzione

String.contains : string -> char -> bool = <fun>

del modulo String, per vedere se un carattere è contenuto in una data stringa.

Tale funzione la utilizziamo internamente ad un programma che fa una ricorsione sulla lista di stringhe per separarle e poter iterare sulle stringhe singole. Utilizziamo un if-then-else come cortocircuito, se almeno una parola ritorna true allora terminiamo.

let rec prog a b s_list = 
     match s_list with
      [] -> false
    | x::xs -> if (string_doubleconf a b x) 
               then true else (prog a b xs);;

# val prog : char -> char -> string list -> bool = <fun>

Si potrebbe comprimere ulteriormente tale funzione, ma penso così sia più chiara.

facendo una prova:

# prog 'e' 'f' ["abc";"add";"ecf"];;
- : bool = true
# prog 'f' 'a' ["abc";"add";"ecf"];;
- : bool = false

Leggi e vedi cosa è chiaro o meno.

Per gli automi (DFA) dai un'occhiata per il momento al primo risultato che esce da google: http://stackoverflow.com/questions/5840 ... a-in-ocaml (le prima quattro righe del type) è la banale definizione, prova a tradure il programma abozzando qualcosa.

EDIT:
Rileggendo il testo si potrebbe interpretare in altro modo:

il programma mi restituisca TRUE se esse sono presenti almeno una volta nelle parole altrimenti FALSE se non sono presenti

l'almeno una volta è inteso come dipendente dalla parola o dalla lista?
Perchè nel caso sopra io ho interpretato che è sensibile alla parola. Se almeno in una parola sono contenute entrambe le lettere torna true e termina.
Ma forse potrebbe essere un forall, stampare a video tutto, quando una parola è true e quando false, cosa che non è molto di un linguaggio funzionale... Forse sono solo dissertazione per l'orario ma vedi se il tuo docente ha detto qualcosa riguardo a quanto ho scritto nell'edit.

[apatriarca]

In effetti il testo non mi sembra molto chiaro. Scrivendo il programma in haskell (non conosco Caml), si potrebbe interpretare sia come hai fatto tu nella prima descrizione

prog c d ss = any (string_doubleconf c d) ss

sia come

prog c d ss = all (string_doubleconf c d) ss

in cui le due lettere devono essere presenti almeno una volta in ogni parola sia come

prog c d ss = any (c `elem` ss) || any (d `elem` ss)

in cui ogni parola deve essere separatamente presente in almeno una parola delle due liste. Probabilmente esistono anche altre interpretazioni possibili (e tanti modi diversi di implementare queste idee...).

P.S. all e any restituiscono True se la funzione booleana passata come primo argomento è vera rispettivamente su tutti o su almeno uno degli elementi della lista passata come secondo argomento. `elem` è la versione infissa della funzione che corrisponde a String.contains in Caml. Per il resto c e d sono Char e ss una lista di stringhe. string_doubleconf che ho tralasciato è la funzione descritta da hamming_burst.

[hamming_burst]

"apatriarca":In effetti il testo non mi sembra molto chiaro. Scrivendo il programma in haskell (non conosco Caml), si potrebbe interpretare sia come hai fatto tu nella prima descrizione

prog c d ss = any (string_doubleconf c d) ss

sia come

prog c d ss = all (string_doubleconf c d) ss

in cui le due lettere devono essere presenti almeno una volta in ogni parola

tradotto in O'Caml non è molto diverso:

let progAny a b s_list = List.exists (string_doubleconf a b) s_list;;
let progAll a b s_list = List.for_all (string_doubleconf a b) s_list;;

Invece:

"apatriarca":sia come

prog c d ss = any (c `elem` ss) || any (d `elem` ss)

in cui ogni parola deve essere separatamente presente in almeno una parola delle due liste. Probabilmente esistono anche altre interpretazioni possibili (e tanti modi diversi di implementare queste idee...).

P.S. all e any restituiscono True se la funzione booleana passata come primo argomento è vera rispettivamente su tutti o su almeno uno degli elementi della lista passata come secondo argomento. `elem` è la versione infissa della funzione che corrisponde a String.contains in Caml. Per il resto c e d sono Char e ss una lista di stringhe. string_doubleconf che ho tralasciato è la funzione descritta da hamming_burst.

questo è molto diverso e direi più complicata da tradurre in OCaml dall'Haskell. Il tipo di scrittura infisso mi pare non sia possibile, anche se simulabile in altro modo.

Vedendo la tipizzazione:

elem :: Eq a => a -> [a] -> Bool

non capisco una cosa, si aspetta un tipo a' ed una lista dello stesso tipo.
Quindi come scritto c: char e ss: string list

(c `elem` ss) 

ha un conflitto di tipizzazione perchè:

char -> [char] -> Bool

dovrebbe esser il tipo corretto, quindi ss è una char list.
invece quello che passiamo è:

char -> [string] -> Bool 

Oppure intendevi altro... perchè anche any ha una scoping parziale e il secondo parametro dovrebbe essere unbound.
Se ho capito correttamente comunque in OCaml si tradurrebbe tipo così:

let progAp a b list = List.exists ((fun a' s -> String.contains s a')a) list 
                      || List.exists ((fun b' s -> String.contains s b')b) list;;

con una funzione anonima parziale, simula l'infisso di elem... (comunque interessante non ero a conoscenza od almeno non ricordo di questo tipo di funzioni in linguaggi funzionali).

[apatriarca]

L'ultimo codice l'ho scritto sbagliato.. ss doveva stare fuori dalle parentesi esattamente come nel primo codice.. La scrittura infissa in realtà non cambia molto le cose.. Si può scrivere (c `elem`) oppure (elem c) e significano esattamente la stessa cosa. In haskell si utilizza spesso la notazione infissa con alcune funzioni come questa, la divisione intera o il modulo per richiamare la notazione matematica. Quindi il codice corretto avrebbe dovuto essere:

prog c d ss = any (c `elem`) ss || any (d `elem`) ss

Non vedo sinceramente perché questo codice dovrebbe essere più complicato da scrivere degli altri in Caml..

[hamming_burst]

"apatriarca":L'ultimo codice l'ho scritto sbagliato.. ss doveva stare fuori dalle parentesi esattamente come nel primo codice.. La scrittura infissa in realtà non cambia molto le cose.. Si può scrivere (c `elem`) oppure (elem c) e significano esattamente la stessa cosa. In haskell si utilizza spesso la notazione infissa con alcune funzioni come questa, la divisione intera o il modulo per richiamare la notazione matematica. Quindi il codice corretto avrebbe dovuto essere:

prog c d ss = any (c `elem`) ss || any (d `elem`) ss

Non vedo sinceramente perché questo codice dovrebbe essere più complicato da scrivere degli altri in Caml..

Perchè in Haskell la tipizzazione è diversa e questi spiega anche che l'errore che dicevo non è vero, infatti è correto il tuo codice in quella parte.

type String = [Char]	Source
A String is a list of characters. String constants in Haskell are values of type String.  

In Ocaml non esiste tale equivalenza e le funzioni tipizzate su liste non possono essere utilizzate sulle Stringhe, infatti esistono due moduli appositi. Non è che sia complicato, ma non è immediato se si vuole una traduzione passando per una simulazione di elem.

In OCaml elem equivalerebbe (tranne per la caratteristica di infisso) a:

List.mem : 'a -> 'a list -> bool
mem a l is true if and only if a is equal to an element of l.

[apatriarca]

Ma era sbagliato.. elem ha tipo a -> [a] -> Bool e restituisce vero se il primo argomento è contenuto nel secondo. Per cui nel primo codice avevo c che era di tipo Char e ss che era di tipo [[Char]] e non sono quindi compatibili. Anche fosse stato corretto avrei comunque dovuto usare or al posto di any. Mi sembra comunque che a parte i nomi più lunghi per le funzioni il codice haskell che ho scritto non è diverso dal tuo in Caml:

let progAp a b list = List.exists ((fun a' s -> String.contains s a') a) list 
                      || List.exists ((fun b' s -> String.contains s b') b) list;;

Ma in Caml non esiste una funzione che scambia gli ultimi due argomenti di una funzione? Qualcosa tipo la funzione flip nell'esempio seguente (spero di aver scritto giusto):

let flip f a b = f b a;;
let progAp a b list = List.exists (flip String.contains a) list 
                      || List.exists (flip String.contains b) list;;

EDIT: Stiamo comunque andando un po' OT..

[hamming_burst]

"apatriarca":Ma era sbagliato.. elem ha tipo a -> [a] -> Bool e restituisce vero se il primo argomento è contenuto nel secondo. Per cui nel primo codice avevo c che era di tipo Char e ss che era di tipo [[Char]] e non sono quindi compatibili. Anche fosse stato corretto avrei comunque dovuto usare or al posto di any.

c'è stata un po' di confusione. Intedevo dopo la tua correzione, invece hai ragione nella tua prima versione a tipizzare così...

"apatriarca":Mi sembra comunque che a parte i nomi più lunghi per le funzioni il codice haskell che ho scritto non è diverso dal tuo in Caml:

let progAp a b list = List.exists ((fun a' s -> String.contains s a') a) list 
                      || List.exists ((fun b' s -> String.contains s b') b) list;;

ma il problema rimane. Non c'è compatibilità diretta tra la definizione di elem e String.contains. Uno lavora su liste (in particolare anche su char list) ed il secondo solo su stringhe.

Per una conversione esatta si dovrebbe utilizzare una funzione apposita string -> char list. Es questa

let explode s =
  let rec exp i l =
    if i < 0 then l else exp (i - 1) (s.[i] :: l) in
  exp (String.length s - 1) [];;

Con l'utilizzo poi di List.mem che come detto è l'equivalente di elem:

let progAp a b list = List.exists ((fun a' s -> List.mem a' (explode s)) a) list 
                      || List.exists ((fun b' s -> List.mem b' (explode s)) b) list;

"apatriarca":Ma in Caml non esiste una funzione che scambia gli ultimi due argomenti di una funzione?

dovrei controllare...

cmq è vero siamo un po' ot oramai...

[apatriarca]

Però quello che non capisco è perché vorresti fare una conversione diretta tra i due in quel modo. Dal punto di vista astratto stiamo comunque verificando se un carattere appartiene alla lista, indipendentemente da come questa stringa è rappresentata. Volendo in haskell avrei potuto usare il tipo ByteString che è nella maggior parte dei casi più efficiente e quindi scrivere B.elem al posto di elem (supponendo di aver importato Data.ByteString come B ovviamente..). Il codice sarebbe stato pressoché lo stesso, ma ora la stringa non è più una lista ma altro.

Per passare la stringa all'automa potrebbe invece essere abbastanza utile trasformare la stringa in lista. Non mi sembra dopotutto immediato estrarre un carattere per volta da una stringa in Caml. Però probabilmente ragiono troppo con una mentalità legata ad Haskell in cui le liste sono in situazioni come questa sostanzialmente free essendo generate in base alla necessità.

[hamming_burst]

"apatriarca":Però quello che non capisco è perché vorresti fare una conversione diretta tra i due in quel modo.

era solo per sottolineare la conversione Haskell -> O'Caml e far notare la differenza (non per efficienza od altro difatti quella conversion è lenta). Diciamo questioni di lana caprina (cit.) e null'altro.

"apatriarca":Per passare la stringa all'automa potrebbe invece essere abbastanza utile trasformare la stringa in lista. Non mi sembra dopotutto immediato estrarre un carattere per volta da una stringa in Caml.

esatto. Ci sono funzioni apposite di mappatura e non c'è accesso diretto ai singoli caratteri.

"apatriarca":Però probabilmente ragiono troppo con una mentalità legata ad Haskell in cui le liste sono in situazioni come questa sostanzialmente free essendo generate in base alla necessità.

infatti sono due linguaggi differenti nella teoria, mi pare che ne avevamo anche discusso su questo tempo fa

[Marco89__1]

"hamming_burst":
l'almeno una volta è inteso come dipendente dalla parola o dalla lista?
Perchè nel caso sopra io ho interpretato che è sensibile alla parola. Se almeno in una parola sono contenute entrambe le lettere torna true e termina.
Ma forse potrebbe essere un forall, stampare a video tutto, quando una parola è true e quando false, cosa che non è molto di un linguaggio funzionale... Forse sono solo dissertazione per l'orario ma vedi se il tuo docente ha detto qualcosa riguardo a quanto ho scritto nell'edit.

Grazie intanto per le risposte!

Allora "l'almeno una volta" è sensibile alla parola, hai interpretato bene. Purtroppo adesso non posso provare il codice, domattina rispondo per bene

[Marco89__1]

Sto provando il codice, questa parte a livello teorico mi torna :

let rec prog a b s_list = 
     match s_list with
      [] -> false
    | x::xs -> if (string_doubleconf a b x) 
               then true else (prog a b xs);;

# val prog : char -> char -> string list -> bool = <fun>

però la funzione :

let string_doubleconf c1 c2 string = (String.contains string c1) && (String.contains string c2);;

# val string_doubleconf : char -> char -> string -> bool = <fun>

mi restituisce sempre errore, sicuro che sia proprio CAML?

Credo che dovrei usare la funzione member per la ricerca delle due lettere nelle parole.

[hamming_burst]

"Marco89__":
mi restituisce sempre errore, sicuro che sia proprio CAML?

riporta qui cosa dice l'interprete, così capiamo...
Dice che il module String è unbound?

"Marco89__":Credo che dovrei usare la funzione member per la ricerca delle due lettere nelle parole.

le veci di member (List.mem) le fa String.contains

EDIT:
ok ho letto ora più attentamente la dispensa che mi avevi inviato, utilizzi Caml Light 0.73
il programma va riscritto con alcune convenzioni un po' più restrittive.