C'è un modo per affermare che un operatore è commutativo, in modo da non dover fornire definizioni identiche per entrambe le direzioni? Per esempio:Proprietà commutativa per gli operatori Haskell?
data Nat = Zero | Succ Nat
(+) :: Nat -> Nat -> Nat
Zero + x = x
x + Zero = x
...
Qui, c'è un modo tale che non avrei dovuto dare entrambe le definizioni, che uno di loro sarebbe implicito dagli altri? C'è un modo per affermare che fn = flip fn?
Non è necessario che questo operatore addizione, ma in generale si può effettuare una funzione commutativa senza implementare tutti i casi capovolte aggiungendo un'equazione finale che lancia gli argomenti:
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
Tuttavia, lo svantaggio è che se si dimentica per trattare un caso, questo porta facilmente ad un ciclo infinito:
adjacent A B = True
adjacent B C = True
adjacent x y = adjacent y x
Qui, adjacent A C chiamerebbe adjacent C A, che avrebbe chiamato adjacent A C, e così via. E il modello di GHC corrisponde al controllo di esaustività (-fwarn-incomplete-patterns o -Wall) non ti aiuterà qui.
Credo che si potrebbe aggiungere un ulteriore argomento per prevenire loop:
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
Ora GHC si lamenterà se non si aggiunge l'equazione go Reverse per gestire il caso in cui si ha commutato ma c'era ancora alcuna corrispondenza.
Ma penso che questo sia adatto solo per le funzioni con un numero elevato di casi, altrimenti è molto più semplice enumerarli tutti.
Perfetto e semplice, grazie! Non so perché non ci ho pensato io stesso. –
Inoltre, GHC è molto cauto nell'integrare le funzioni ricorsive (perché potrebbe non fermarsi mai!), Quindi l'utilizzo di questa tecnica potrebbe interferire con le ottimizzazioni del compilatore. Anche se naturalmente è anche possibile che GHC capisca che è davvero * non * ricorsivo, e finirà con l'inlining, ma non sono sicuro che sia abbastanza intelligente. – dfeuer
per dirla come una risposta: Sì, se si implementa inoltre regolare, si finisce automaticamente con un'operazione commutativa:
(+) :: UInt -> UInt -> UInt
Zero + x = x
(Succ s) + x = s + (Succ x)
Questa operazione è commutativa, anche se non è efficace in entrambe le direzioni, significato che "big number as UInt" + Zero impiega più tempo di Zero + "big number as UInt" perché l'operatore di addizione è definito in questo modo.
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
Un modo semplice per risolvere questo problema è quello di definire inoltre il modo in cui l'avete fatto, che definisce esplicitamente commutativity.
È possibile definire l'aggiunta normalmente e ottenere la commutatività (lenta) gratuitamente. – ThreeFx
Inoltre, questo ha già una risposta [qui] (http://stackoverflow.com/questions/29210248/haskell-defining-commutative-functions-how-to-consider-actual-arguments-by-co). (È più generico del tuo caso d'uso, quindi probabilmente devi fare qualche ricerca su come utilizzare il pacchetto suggerito) – ThreeFx
Se si considera la pigrizia quasi nessuna operazione è completamente commutativa perché tipicamente 'f undefined x' può essere differente da' fx undefined' a causa del fatto che la corrispondenza del modello è essenzialmente sequenziale. Questo è il motivo per cui è così difficile ottenere la piena astrazione tra semantica operativa e denotativa dei linguaggi funzionali: nella semantica denotativa si includono funzioni come parallele o ecc. Che non possono essere effettivamente definite nella lingua. – Bakuriu