Modo efficiente per scrivere istanze di ordinazione?

Question

Sto lavorando ad un'esercitazione di base Haskell configurata come segue: viene creata una definizione di dati, dove Zero è dichiarato come e una serie di numeri (stampati per nome, quindi, ad esempio, four) fino a ten è costruito con questo.

Non ho avuto troppi problemi nel comprendere come funziona la dichiarazione delle istanze Eq (a parte il fatto che non è stata fornita una spiegazione esatta della sintassi), ma ho difficoltà a dichiarare tutte le istanze di cui ho bisogno per Ord - Devo essere in grado di costruire un ordinamento sull'intero insieme di numeri, in modo tale da ottenere True se inserisco "dieci> nove" o qualcosa del genere.

In questo momento, ho questo snippet di codice. Le prime due righe dovrebbero essere corrette, poiché le ho copiate (come dovevo) dall'esercizio stesso.

instance Ord NaturalNumber where 
    compare Zero Zero = EQ 
    compare Zero (S Zero) = LT 
    compare (S Zero) Zero = GT 
    compare x (S x) = LT 

Le prime quattro linee funzionano bene, ma non possono trattare i casi come "confronto quattro cinque", e qualcosa di simile a quello che ho scritto nella scorsa non funziona anche se di tipo I in qualcosa di simile compare four four = EQ: viene visualizzato un errore "definizioni in conflitto", presumibilmente perché lo x viene visualizzato due volte. Se scrivo qualcosa come compare two one = GT, invece, ricevo un avviso di "corrispondenza modello (i) sono sovrapposti", ma funziona. Tuttavia, ottengo anche il risultato GT quando inserisco compare one two nella reale piattaforma Haskell, quindi chiaramente qualcosa non funziona. Ciò accade anche se aggiungo compare one two = LT sotto quella linea.

Così chiaramente non riesco a completare questa descrizione delle istanze di Ord scrivendo ogni istanza di cui potrei aver bisogno, e anche se potessi, sarebbe incredibilmente inefficiente scrivere tutte le 100 istanze a mano.

Qualcuno può darmi un suggerimento su come posso risolvere questo problema e terminare la costruzione di un meccanismo di ordinazione?

Answer 1

Ciò su cui questo compito si concentra è la ricerca di casi base e regole di ricorsione. Le prime due righe hanno dato erano

instance Ord NaturalNumber where 
    compare Zero Zero = EQ 

Questo è il caso base prima, in parole:

zero è uguale a zero

Gli altri due casi di base sono:

zero è inferiore al successore di qualsiasi NaturalNumber

il successore di qualsiasi NaturalNumber è maggiore di zero

nota che le linee tre e quattro solo dire che 0 < 1 e 1 > 0, ma nulla di qualsiasi altro numero diverso da zero.

La regola di ricorsione, quindi, è che non fa alcuna differenza se si confrontano due numeri diversi da zero, oppure i numeri che sono successori di:

confrontando 1 + x e 1 + y è lo stesso che il confronto x e y.

Codificarlo in Haskell dovrebbe darti la soluzione a questo esercizio.

Answer 2

La funzione compare deve essere ricorsiva. Volete che il vostro ultimo caso catturi la situazione in cui entrambi gli argomenti sono il successore di qualcosa, e poi recitate su ciò di cui sono il successore. Inoltre, il tuo centro due casi, non sono probabilmente ciò che si vuole, in quanto saranno catturare solo i seguenti casi:

1. 1 > 0
2. 0 < 1

Vorreste questo per essere più generale, in modo da che è possibile gestire casi come:

1. S x > 0, per tutti x
2. 0 < S x, per tutti x

Answer 3

Avrai bisogno di organizzare le istanze in modo tale da coprire tutti i modelli possibili. Per rendere più semplice, ricordare come i numeri sono definiti:

one = S Zero 
two = S one -- or S (S Zero) 

e pensare in termini di S e Zero, non one, two ecc (sono semplicemente alias).Una volta fatto questo, dovrebbe diventare chiaro che vi state perdendo un caso come:

compare (S x) (S y) = compare x y 

Edit: Come Jakob Runge notato, anche le seguenti clausole di base dovrebbero essere migliorate:

compare Zero (S Zero) = LT 
compare (S Zero) Zero = GT 

Come sono scritti, consentono il confronto solo tra zero e uno. Dovresti cambiarli per coprire il confronto tra zero e qualsiasi numero positivo:

compare Zero (S _) = LT 
compare (S _) Zero = GT