Esiste una soluzione alternativa per la mancanza di backtracking della classe di tipi?

Question

In this talk around the 1:20 mark, Edward Kmett menziona la mancanza di "classe backtracking" in Haskell. Si consideri il problema di "set uguaglianza" (in cui l'ordine e la molteplicità sono ignorati) implementati sulle liste:

equals :: [a] -> [a] -> Bool 

Per la natura delle classi di tipo non posso fornire un confronto inefficiente O (n²) se tutto quello che abbiamo è Eq a ma confrontare in modo efficiente gli elenchi in O (n log n) se disponiamo di Ord a.

Ho capito perché una tale struttura sarebbe problematica. Allo stesso tempo, Edward dice che ci sono "trucchi che potresti giocare" menzionando per esempio le famiglie di tipi.

Quindi la mia domanda è, quale sarebbe una soluzione per ottenere lo stesso effetto:

• una (inefficiente) implementazione predefinita è previsto
• se l'utente può fornire alcune informazioni aggiuntive sul tipo, abbiamo "sblocca" un'implementazione più efficiente

Questa soluzione alternativa non deve necessariamente utilizzare le classi di tipi.

Edit: Qualcuno ha suggerito semplicemente fornendo equals e efficientEquals come due metodi distinti. In generale sono d'accordo che questo è l'approccio più idiomatico di Haskell. Tuttavia, non sono convinto che ciò sia sempre possibile. Per esempio, che cosa se il metodo equals di cui sopra è a sua volta parte di una classe tipo:

class SetLike s where 
    equals :: Eq a => s a -> s a -> Bool 

Si supponga che questa classe è stata fornita da qualcun altro, quindi non posso semplicemente aggiungere una nuova funzione al typeclass. Ora voglio definire l'istanza per []. So che lo può sempre fornire un'implementazione di equals, non importa quali siano i vincoli su a ma non posso dire alla mia istanza di utilizzare la versione più efficiente se sono disponibili ulteriori informazioni su a.

Forse potrei avvolgere la lista in un newtype e taggarla con alcune informazioni di tipo aggiuntive?

Answer 1

Nello scenario dalla tua modifica, si potrebbe usare un GADT come prova della vostra Ord vincolo:

{-# LANGUAGE GADTs #-} 

import Data.List 

class SetLike s where 
    equals :: Eq a => s a -> s a -> Bool 

data OrdList a where 
    OrdList :: Ord a=> [a] -> OrdList a 

instance SetLike OrdList where 
    equals (OrdList a) (OrdList b) = sort a == sort b 

E per il divertimento qui c'è qualcosa che utilizza fa uso della OverlappingInstances trucco che ho già detto nel mio commento. Ci sono molti modi per fare questo genere di cose:

{-# LANGUAGE DefaultSignatures, OverlappingInstances, UndecidableInstances, MultiParamTypeClasses, FlexibleInstances #-} 

import Data.List 

class Equals a where 
    equals :: [a] -> [a] -> Bool 

    default equals :: Ord a=> [a] -> [a] -> Bool 
    equals as bs = sort as == sort bs 

instance Equals Int 
instance Equals Integer 
instance Equals Char 
-- etc. 

instance (Eq a)=> Equals a where 
    equals = error "slow version"