Czy istnieje sposób na stwierdzenie, że operator jest przemienny, tak że nie muszę podawać identycznych definicji dla obu kierunków? Na przykład:Dobra komutacyjne dla operatorów Haskell?
data Nat = Zero | Succ Nat
(+) :: Nat -> Nat -> Nat
Zero + x = x
x + Zero = x
...
Tutaj jest jakiś sposób taki, że nie będę musiał dać obu tych definicjach, że jeden z nich będzie domniemanych od drugiego? Czy jest jakiś sposób na stwierdzenie, że fn = flip fn?
To nie jest konieczne do tego operator dodawania, ale w ogóle można zrobić funkcją przemienne bez realizacji wszystkich przewracanej przypadki dodając ostateczną równanie, które odwraca argumenty:
data X = A | B | C
adjacent A B = True
adjacent B C = True
adjacent A C = False
adjacent x y = adjacent y x -- covers B A, C B, and C A
Jednak minusem jest to, że jeśli zapomnisz obsłużyć przypadek, to łatwo prowadzi do nieskończonej pętli:
adjacent A B = True
adjacent B C = True
adjacent x y = adjacent y x
Tutaj adjacent A C nazwałbym adjacent C A, który nazwałbym adjacent A C, i tak dalej. Wzorzec dopasowania GHC do sprawdzania wyczerpania (-fwarn-incomplete-patterns lub -Wall) nie pomoże tutaj.
Chyba można dodać dodatkowy argument, aby zapobiec pętli:
data Commute = Forward | Reverse
adjacent = go Forward
where
go _ A B = True
go _ B C = True
go Forward x y = go Reverse y x -- try to commute
go Reverse _ _ = False -- commuting failed
Teraz GHC będzie narzekać, jeśli nie dodać równanie go Reverse obsłużyć przypadek gdzie zamieniono ale nadal nie było meczu.
Ale myślę, że jest to odpowiednie tylko dla funkcji z dużą liczbą przypadków - w przeciwnym razie dużo lepiej jest po prostu wyliczyć je wszystkie.
Idealne i proste, dzięki! Nie wiem, dlaczego sam o tym nie myślałem. –
Ponadto GHC bardzo nie zwraca uwagi na funkcje rekursywne (ponieważ może się nigdy nie zatrzymać!), Więc użycie tej techniki może zakłócić optymalizacje kompilatora. Chociaż oczywiście jest możliwe, że GHC zorientuje się, że to naprawdę * nie * rekursywne, i kończy się na inline, ale nie jestem pewien, czy to całkiem sprytne. – dfeuer
Aby umieścić go jako odpowiedź: Tak, jeśli wdrożenie regularnego Ponadto automatycznie skończyć z przemiennej pracy:
(+) :: UInt -> UInt -> UInt
Zero + x = x
(Succ s) + x = s + (Succ x)
Ta operacja jest przemienne, choć nie jest skuteczny w obie strony, co oznacza to, że "big number as UInt" + Zero trwa dłużej niż Zero + "big number as UInt", ponieważ operator dodawania jest zdefiniowany w ten sposób.
ghci> :set +s
ghci> bignum + Zero
number as uint
(0.01 secs, 4,729,664 bytes) -- inefficient O(n) operation
ghci> Zero + bignum
number as uint
(0.00 secs, 0 bytes) -- instant constant operation
Łatwym sposobem na naprawienie tego jest zdefiniowanie dodawania w taki sposób, jak to tylko możliwe, wyraźne definiowanie przemijalności.
Można zdefiniować dodawanie normalnie i uzyskać (wolną) komutatywność za darmo. – ThreeFx
Również to już ma odpowiedź [tutaj] (http://stackoverflow.com/questions/29210248/haskell-defining-commutative-functions-how-to-consider-actual-arguments-by-co). (Jest bardziej ogólny niż Twój przypadek użycia, więc prawdopodobnie będziesz musiał przeprowadzić pewne badania, aby skorzystać z sugerowanego pakietu) – ThreeFx
Jeśli weźmiesz pod uwagę leniwość prawie żadna operacja nie jest całkowicie przemienna, ponieważ zazwyczaj 'f niezdefiniowane x' może być inne niż' fx undefined' ze względu na fakt, że dopasowywanie wzorców jest zasadniczo sekwencyjne. Z tego powodu tak trudno jest uzyskać pełną abstrakcję pomiędzy operatywną i denotacyjną semantyką języków funkcjonalnych: w denotacyjnej semantyce włącza się funkcje takie jak równoległe lub itd., Które w rzeczywistości nie mogą być zdefiniowane w języku. – Bakuriu