Czy istnieje obejście problemu z brakiem śledzenia klasy typu?

Question

W this talk around the 1:20 mark, Edward Kmett wspomina o braku "backtrackingu klasy" w Haskell. Rozważ problem „set równości” (gdzie kolejność i wielość są pomijane) realizowany na listach:

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

Przez charakteru zajęć typu I nie może dostarczyć nieefektywne O (n²) porównania, jeśli wszystko, co mamy jest Eq a ale wydajnie porównaj listy w O (n log n), jeśli mamy Ord a.

Zrozumiałem, dlaczego taki obiekt byłby problematyczny. W tym samym czasie, Edward mówi, że istnieją "sztuczki, które można grać", wspominając na przykład rodziny typu.

Stąd moje pytanie, co byłoby obejście aby osiągnąć ten sam efekt:

• An (nieskuteczny) Domyślna implementacja jest
• jeżeli użytkownik może dostarczyć dodatkowych informacji o rodzaju, my "odblokuj" bardziej wydajną implementację

To rozwiązanie nie musi koniecznie używać klas typów.

Edit: Niektórzy ludzie po prostu zaproponował dostarczenie equals i efficientEquals jako dwóch odrębnych metod. Ogólnie zgadzam się, że jest to bardziej podejście Haskella-idiomatyczne. Jednak nie jestem przekonany, że jest to zawsze możliwe. Na przykład, co jeśli metoda equals powyżej sama jest częścią klasy typu:

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

Załóżmy, że klasa ta została przekazana przez kogoś innego, więc nie można po prostu dodać nową funkcję do typeclass. Teraz chcę zdefiniować instancję dla []. Wiem, że [] zawsze może zapewnić implementację equals bez względu na ograniczenia, które istnieją na a, ale nie mogę powiedzieć, aby moja instancja używała bardziej wydajnej wersji, jeśli jest dostępna większa ilość informacji o a.

Może mogę zawinąć listę w nowy typ i oznaczyć ją dodatkowymi informacjami o typie?

Answer 1

W scenariuszu ze swojej zmiany, można użyć GADT jako dowód swojej Ord przymusu:

{-# 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 

A dla zabawy tutaj coś, co wykorzystuje korzysta z OverlappingInstances sztuczki wspominam w moim komentarzu. Istnieje wiele sposobów na zrobienie tego rodzaju rzeczy:

{-# 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"