Dlaczego konieczna jest redukcja kontekstu?

Question

Właśnie przeczytałem this paper ("Klasy typów: eksploracja przestrzeni projektowej" autorstwa Peytona Jonesa & Jones), co wyjaśnia niektóre problemy związane z wczesnym systemem Haskella i jego ulepszaniem.

Wiele problemów, które podnoszą, jest związanych z redukcją kontekstu , co jest sposobem na zmniejszenie zestawu ograniczeń w stosunku do deklaracji instancji i funkcji, zgodnie z relacją "odwrotnego powiązania".

np. jeśli masz gdzieś instance (Ord a, Ord b) => Ord (a, b) ..., wtedy w kontekstach, Ord (a, b) zostaje zredukowane do {Ord a, Ord b} (redukcja nie zawsze zmniejsza liczbę ograniczeń).

Nie rozumiałem z artykułu, dlaczego ta redukcja była konieczna.

Cóż, zebrałem, że został użyty do wykonania jakiejś kontroli typu. Kiedy masz zredukowany zestaw ograniczeń, możesz sprawdzić, czy istnieje pewne wystąpienie, które może je spełnić, w przeciwnym razie jest to błąd. Nie jestem zbyt pewny, jaką jest wartość dodaną, ponieważ zauważysz problem na stronie użytkowania, ale w porządku.

Ale nawet jeśli musisz zrobić to sprawdzić, dlaczego użyć wyniku redukcji wewnątrz wywnioskowane typy? Wskazuje na to, że prowadzi to do niezrozumiałych wnioskowych typów.

Artykuł jest dość pradawny (1997), ale o ile wiem, redukcja kontekstu nadal stanowi problem. Specyfikacja Haskell 2010 wspomina zachowanie wnioskowania wyjaśnione powyżej (link).

Dlaczego więc to robi?

Answer 1

Nie wiem, czy to jest Przyczyn, koniecznie, ale można by to uznać za przyczynę: we wczesnych Haskell, typ podpisów mógł zawierać tylko "proste" ograniczenia, a mianowicie nazwę klasy typu zastosowaną do zmienna typu. Tak więc, na przykład, wszystkie z nich były w porządku:

Ord a => a -> a -> Bool 
Eq a => a -> a -> Bool 
Graph gr => gr n e -> [n] 

Ale żaden z nich:

Ord (Tree a) => Tree a -> Tree a -> Bool 
Eq (a -> b) => (a -> b) -> (a -> b) -> Bool 
Graph Gr => Gr n e -> [n] 

Myślę, że było to uczucie wtedy - i jeszcze dziś, a także - że pozwalając Kompilator, aby wywnioskować typ, którego nie można było ręcznie napisać, byłby trochę niefortunny. Redukcja kontekstu była sposobem na przekształcenie powyższych sygnatur albo w te, które można by napisać ręcznie, a także, jako błąd informacyjny, lub. Na przykład, ponieważ można by rozsądnie mieć

instance Ord a => Ord (Tree a) 

w zakresie, możemy włączyć nielegalnej podpis Ord (Tree a) => ... do podpisu prawnego Ord a => .... Z drugiej strony, jeśli nie mamy żadnej instancji Eq dla funkcji w zakresie, można zgłosić błąd dotyczący typu, który został wywnioskowany, aby wymagał Eq (a -> b) w swoim kontekście.

ten ma kilka innych zalet:

1. Intuicyjnie przyjemny. Wiele reguł redukcji kontekstu nie zmienia się, czy typ jest legalny, ale odzwierciedlają to, co ludzie zrobiliby przy pisaniu tego typu. Zastanawiam się tutaj nad regułami deduplikacji i subsumption, które pozwolą Ci skręcić, np.(Eq a, Eq a, Ord a) w tylko Ord a - transformacja, którą zdecydowanie chcielibyśmy zrobić dla czytelności.
2. To często może złapać głupie błędy; zamiast wnioskować o typie takim jak Eq (Integer -> Integer) => Bool, którego nie można spełnić zgodnie z prawem, można zgłosić błąd taki jak Perhaps you did not apply a function to enough arguments?. O wiele bardziej przyjazny!
3. Staje się zadaniem kompilatora, aby wskazać, co poszło nie tak. Zamiast wnioskować o skomplikowanym kontekście, jak na przykład o tym, że kontekst nie jest satysfakcjonujący, zamiast tego jest on zmuszony ograniczyć to do ograniczeń składowych; zamiast tego będzie narzekać, że nie możemy stwierdzić, że nie można ustalić Eq (Grizwump a) z istniejącego kontekstu - o wiele dokładniejszego i łatwiejszego do wykonania błędu.

Answer 2

Myślę, że jest to rzeczywiście pożądane w słowniku przekazującym implementację. W takiej implementacji "słownik", czyli krotka lub rekord funkcji, jest przekazywany jako niejawny argument dla każdego ograniczenia klasy typów w typie zastosowanej funkcji.

Teraz pytanie brzmi po prostu, kiedy i jak tworzone są te słowniki. Zauważ, że dla prostych typów, takich jak Int z konieczności, wszystkie słowniki dla jakiejkolwiek klasy typu Int jest instancją będą stałą. Nie dotyczy to typów sparametryzowanych, takich jak listy, Maybe lub krotek. Jest oczywiste, że aby pokazać krotkę, na przykład, instancje Show rzeczywistych elementów krotek muszą być znane. Stąd taki słownik polimorficzny nie może być stały.

Wygląda na to, że zasada prowadzenia słownika jest taka, że ​​przekazywane są tylko słowniki dla typów, które pojawiają się jako zmienne typu w typie zastosowanej funkcji. Lub, inaczej mówiąc: nie są replikowane żadne nadmiarowe informacje.

Rozważmy tę funkcję:

f :: (Show a, Show b) => (a,b) -> Int 
f ab = length (show ab) 

Informacje że krotką showable komponentów jest również showable, a tym samym ograniczenie jak Show (a,b) potrzeb nie pojawiają się, gdy już wiemy (Show a, Show b).

Alternatywna implementacja byłaby jednak możliwa, gdyby osoba wywołująca była odpowiedzialna za tworzenie i przekazywanie słowników. To może pracować bez redukcji kontekstowego, tak że typ f wyglądałby następująco:

f :: Show (a,b) => (a,b) -> Int 

Ale to oznaczałoby, że kod do tworzenia słownika krotny musiałyby być powtarzane na każdej stronie połączenia. I łatwo jest wymyślić przykłady, gdzie liczba koniecznych ograniczeń rzeczywiście wzrasta, podobnie jak w:

g :: (Show (a,a), Show(b,b), Show (a,b), Show (b, a)) => a -> b -> Int 
g a b = maximum (map length [show (a,a), show (a,b), show (b,a), show(b,b)]) 

Pouczające jest wdrożenie systemu typu klasy/instancji z rzeczywistymi zapisów, które są wyraźnie minęła. Na przykład:

data Show' a = Show' { show' :: a -> String } 
showInt :: Show' Int 
showInt = Show' { show' = intshow } where 
     intshow :: Int -> String 
     intshow = show 

Gdy to zrobisz, prawdopodobnie z łatwością zauważysz potrzebę "redukcji kontekstu".