2012-02-25 21 views
5

Sono quasi sicuro di avere un ciclo infinito causato dal mio caso "predefinito". Sto usando la ricorsione in tutti i casi. Quale è destinato a essere, ma solo se la Prop può essere semplificata. Non appena la Prop non può essere semplificata, dovrebbe restituire il tutto.Codice scala infinita scala

Non vedo come posso testare per ulteriori semplificazioni. (Non sono autorizzato ad usare altre librerie, come suggerito nel canale #scala di freenodes).

Qualcuno può spiegare se è il "caso _" che causa il ciclo e come risolverlo? Come posso verificare la possibile semplificazione senza fare un ciclo?

Grazie in anticipo!

risposta

6

Il problema è che si sta tentando di fare due cose in un unico passaggio che devono avvenire in sequenza, applicando la legge di De Morgan (e rimuovendo la doppia negazione) e semplificando ricorsivamente i bambini. Questo è il motivo per cui non è sufficiente inserire uno case And(a, b) => And(simplify(a), simplify(b)) nel tuo match.

provare quanto segue:

val deMorganAndDoubleNegation: Prop => Prop = { 
    case Not(Or(a, b)) => And(Not(a), Not(b)) 
    case Not(And(a, b)) => Or(Not(a), Not(b)) 
    case Not(Not(a)) => a 
    case a => a 
} 

val simplify: Prop => Prop = deMorganAndDoubleNegation andThen { 
    case And(a, b) => And(simplify(a), simplify(b)) 
    case Or(a, b) => Or(simplify(a), simplify(b)) 
    case Not(a) => Not(simplify(a)) 
    case a => a 
} 
+0

Vedo cosa intendi, anche se il mio compito mi dice esplicitamente di usare un oggetto compagno. Prop.simplify (Prop): Prop che restituisce una proposizione semplificata ed equivalente applicando ripetutamente la legge di de Morgan e la doppia elliminazione della negazione all'argomento Proposition La proposta risultante deve soddisfare i requisiti descritti di seguito. Inoltre, il tuo suggerimento non corrisponde completamente i miei docenti rispondono (abbiamo un sistema per eseguire il nostro lavoro contro un test) Vedi: http://pastebin.com/WDuQKreD (anche per il merluzzo completo e al momento) Grazie comunque! – Sander

+0

@Sander: Devi solo aggiungere dei casi per "semplificare" per le altre operazioni (inoltre, mi dispiace non aver capito che questo è compito a casa - non sarei stato così diretto nella mia risposta). –

+0

@Sander: Inoltre, entrambi ereditano da una classe case e hanno una classe case con un costruttore vuoto sono di cattiva forma. 'tratto Prop; l'oggetto case True estende il Prop. è migliore. –

9

È abbastanza ovvio cosa succede e hai ragione con il valore predefinito case. Se il vostro input prop non corrisponde a nessuno dei casi si invoca:

simplify(prop) 

con lo stesso argomento. Poiché in precedenza ha causato una chiamata ricorsiva a simplify() e si sta chiamando la funzione con lo stesso input, viene immesso nuovamente simplify(). Quindi questo non è un ciclo infinito ma mai terminato chiamata ricorsiva:

...simplify(simplify(simplify(simplify(simplify(simplify(simplify(prop))))))) 

Tuttavia la correzione (in base al codice) è semplice:

if (simplify(prop) == prop) prop 
    else prop 

basta sostituirlo con ...

case _ => prop 

Entrambi i rami restituiscono lo stesso valore. Questo è effettivamente corretto se ci pensi se per un po '. Hai una serie di ottimizzazioni. Se nessuno di questi corrisponde alle tue espressioni significa che non può più essere semplificato. Quindi lo stai restituendo così com'è.

BTW sembra come se si stesse facendo la semplificazione di espressioni booleane utilizzando le classi dei casi. Potrebbe interessarti il ​​mio article dove faccio lo stesso, ma con espressioni aritmetiche.

+0

Grazie per la risposta. Ho provato a farlo. (Mi dispiace, premuto invio, e pubblicato senza volere). Ma in alcuni casi, ad esempio, la semplificazione si traduce in una stringa contenente un nuovo Not (Not (a)), quindi la nuova semplificazione li eliminerebbe. Ma non riesco a farlo funzionare di nuovo quando la loro sembra essere una nuova partita in uno dei casi precedenti ..: \ – Sander

+2

@Sander: puoi mostrarci l'input che non sta semplificando 'Not (Not (a)) '? Questo può essere risolto chiamando 'simplify()' su termini separati come, e.g: per semplificare 'E (Not (Not (a)), b)' è necessario restituire 'E (semplificare (Not (Not (a)), semplificare (b))' (il modello di semplificazione è: 'E (a , b) => E (semplificare (a), semplificare (b)) '. –

+0

@Thomasz' Not (And (Not (a), Not (b))) 'Questo verrà prima semplificato a' Or (Not (Not (a)), Not (Not (b))) 'per quanto posso vedere, il codice deve essere rieseguito per eliminare i nuovi Not (Not (a)) e Not (Not (b)). – Sander

2

Sì, il caso predefinito causa il ciclo. if (simplify(prop) == prop) prop è una linea problematica. Non è necessario testare se può essere ulteriormente semplificato perché quando si è nel caso predefinito vengono tentate tutte le possibili semplificazioni.