Wydajny sposób pisania wystąpień zamawiania?

Question

Pracuję nad podstawowym ćwiczeniem Haskella, które jest ustawione w następujący sposób: definiowana jest definicja danych, gdzie Zero jest zadeklarowana jako NaturalNumber, oraz seria liczb (wydrukowana po nazwie, na przykład four) aż do ten jest skonstruowany z tym.

Nie miałem większych kłopotów ze zrozumieniem, jak działają deklaracje instancji Eq (oprócz braku dokładnego wyjaśnienia składni), ale mam problem z zadeklarowaniem wszystkich potrzebnych instancji dla Ord - Muszę być w stanie zbudować zamówienie na cały zestaw liczb, tak, że dostanę True, jeśli wprowadzę "dziesięć> dziewięć" lub coś podobnego.

W tej chwili mam ten fragment kodu. Pierwsze dwie linie powinny być poprawne, ponieważ skopiowałem je (tak jak powinienem) z samego ćwiczenia.

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

Pierwsze cztery linie działają dobrze, ale nie może zajmować się sprawami jak „porównać cztery pięć”, i coś podobnego do tego, co wpisane w ostatni nie działa nawet wtedy, gdy wpisuję w czymś takim compare four four = EQ: Pojawia się błąd "sprzecznych definicji", prawdopodobnie dlatego, że x pojawia się dwa razy. Jeśli zamiast tego napiszę coś takiego jak compare two one = GT, otrzymam ostrzeżenie "dopasowania wzoru", ale działa. Jednak otrzymuję również wynik GT po wprowadzeniu compare one two do rzeczywistej platformy Haskell, więc wyraźnie coś nie działa. Dzieje się tak, nawet jeśli dodaję compare one two = LT poniżej tego wiersza.

Tak więc nie mogę zakończyć opisu instancji Ord, pisząc każdą możliwą instancję, a nawet gdybym mógł, byłoby niewiarygodnie nieefektywne wypisanie wszystkich 100 wystąpień ręcznie.

Czy ktoś może mi wskazać, w jaki sposób mogę rozwiązać ten problem i dokończyć konstrukcję mechanizmu zamawiania?

Answer 1

Na czym polega to zadanie polega na wyszukiwaniu podstawowych przypadków i reguł rekurencji. Pierwsze dwie linie, które zostały podane były

instance Ord NaturalNumber where 
    compare Zero Zero = EQ 

Jest to pierwszy przypadek bazowy, w słowach:

zerowego jest równa zeru

Pozostałe dwa przypadki bazowe są:

zero jest mniejsze niż następca dowolnego modelu NaturalNumber

następcą dowolnym NaturalNumber jest większa niż zero

pamiętać, że linie trzy i cztery tylko powiedzieć, że 0 < 1 i 1 > 0, ale nic o innych numerach niezerowych.

Reguła rekurencji, to to, że nie ma znaczenia, jeśli porównać dwa niezerowe cyfry lub liczby są one następcy:

porównując 1 + x i 1 + y jest taka sama jak porównując x i y.

Skodyfikowanie tego w Haskell powinno dać ci rozwiązanie tego ćwiczenia.

Answer 2

Twoja funkcja compare musi być rekurencyjna. Będziesz potrzebował ostatniego przypadku, aby uchwycić sytuację, w której oba argumenty są następcą czegoś, a następnie powracają do tego, co jest ich następcą. Dodatkowo środkowym dwa przypadki, to prawdopodobnie nie to, co chcesz, ponieważ będą one przechwytywać tylko następujące przypadki:

1. 1 > 0
2. 0 < 1

chce pan być bardziej ogólnie, tak że można obsługiwać takich przypadkach:

1. S x > 0 dla wszystkich x
2. 0 < S x dla wszystkich x

Answer 3

trzeba uporządkować instancji w sposób, który obejmie wszystkie możliwe wzory. Żeby było prościej, pamiętam jak numery są zdefiniowane:

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

i myśleć w kategoriach S i Zero, nie one, two itp (są one jedynie pseudonimy).Gdy to zrobisz, powinno stać się jasne, że tracisz sprawy jak:

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

Edit: Jakob Runge Jak zauważył również poniższych punktach bazowych należy poprawić:

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

Jak są napisane, pozwalają na porównanie tylko między zerem a jednym. Powinieneś je zmienić, aby pokryć porównanie między zerem a dowolną liczbą dodatnią:

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