Dlaczego Haskell nie jest w stanie uniknąć powtórnej oceny bez ograniczenia monomorfizmu?

14

Niedawno skończyłem learnyouahaskell i starałem się zrozumieć sens ograniczeń monomorfizmu, jak opisano w Wiki Haskell . Wydaje mi się, że rozumiem, w jaki sposób MR może zapobiegać powtarzającym się ocenom, ale nie rozumiem, dlaczego nie można uniknąć tych powtarzanych ocen za pomocą znacznie prostszych środków.

Konkretny przykład, który mam na myśli, to ten używany przez wiki:

f xs = (len,len)
  where
    len = genericLength xs

gdzie genericLengthjest typu Num a => [b] -> a.

Oczywiście genericLength xsdo obliczenia wystarczy tylko raz obliczyć (len,len), ponieważ jest to ta sama funkcja z tymi samymi argumentami. I nie musimy widzieć żadnych inwokacji, faby to wiedzieć. Dlaczego więc Haskell nie może przeprowadzić tej optymalizacji bez wprowadzenia reguły takiej jak MR?

Dyskusja na tej stronie wiki mówi mi, że ma to coś wspólnego z faktem, że Numjest ona typem, a nie konkretnym typem, ale mimo to, czy nie powinno być oczywiste w czasie kompilacji, że funkcja czysta zwróciłaby tę samą wartość - - a zatem ten sam konkretny typ Num - gdy podano dwa razy te same argumenty?

Ixrec
źródło

Odpowiedzi:

11

Jest to ta sama nazwa funkcji, z tymi samymi argumentami, ale potencjalnie różne typy zwracane i implementacje, ponieważ jest polimorficzna. Oznacza to, że jeśli jest wywoływany w kontekście oczekującym typu (Int, MyWeirdCustomNumType)zwracanego, musi go ocenić dwukrotnie, ponieważ implementacja (+)in Intróżni się całkowicie od implementacji (+)in MyWeirdCustomNumType. W pewnym momencie musisz uruchomić fizycznie inny kod.

Dlatego ważne Numjest, aby była to klasa typu. Oznacza to, że masz różne implementacje dla różnych typów. Oznacza to również, że jeśli fjest w bibliotece, nie wie w czasie kompilacji o wszystkich kombinacjach typów, które może wymagać zwrotu.

Tak, tak, musisz zobaczyć wywołania, faby wiedzieć, jakich typów zwrotów użyć. Przez większość czasu można oczekiwać, że będą takie same, dlatego domyślnie wprowadzają ograniczenie monomorfizmu. Można go wyłączyć na te rzadkie okazje, gdy tego nie zrobisz. W praktyce programiści nie pozostawiają tego rodzaju sytuacji, aby i tak wnioskować.

Karl Bielefeldt
źródło
Nie zastanawiałem się nad możliwością f [] :: (Int, Float). Teraz ma to sens. Dziękuję Ci.
Ixrec
1
It's the same function name, with the same arguments, but potentially different return types and implementations, because it's polymorphic.Myślę, że lepszym sposobem patrzenia na to jest to, że instancja klasy jest faktycznie dodatkowym argumentem, genericLengtha kompilator nie jest przekonany, że to te same argumenty w obu wywołaniach.
Doval
Szybkie pytanie poboczne. Jeśli ograniczenie monomorfizmu jest wyłączone, ale później zrobiłeś coś takiego: a = uncurry (==) $ f [1, 2, 3]Czy byłby w stanie zoptymalizować tę witrynę wywołań, aby sprawdzić długość tylko [1, 2, 3]raz? Jeśli tak, to jestem naprawdę zdezorientowany, co tak naprawdę ogranicza cię monomorfizm, a jeśli nie, to dlaczego nie?
średnik