Czy typy są kasowane w Haskell?

13

Haskell ma pojęcie „funkcji ogólnych”, które ma pewne pozorne podobieństwo ze wspólnym seplenieniem - nie mając doświadczenia z Haskellem ani ze wspólnym seplenieniem, mogę tu być bardzo przybliżony. Oznacza to, że można zdefiniować ogólne to_stringnarzędzie do zdefiniowania reprezentacji ciągu dla wszystkich typów. Oczywiście obiekt należy zdefiniować w szczególnych przypadkach, ale istnieje to_stringfunkcja, której podpis jest α → string.

Czy typy są kasowane w Haskell, tak jak w OCaml? Jeśli tak, w jaki sposób implementacja „funkcji ogólnych” w Haskell różni się od implementacji typowego seplenia, gdzie typy są dynamiczne, a zatem nie są usuwane?

Rozumiem, że szczegóły implementacji są specyficzne dla kompilatora, ale prawdopodobnie istnieją przepisy wspólne dla wielu lub wszystkich implementacji.

użytkownik40989
źródło
5
Pamiętaj, że prawdopodobnie nie możesz zdefiniować nietrywialnej funkcji typu a -> String. Bardziej prawdopodobne jest ograniczenie typu, na przykład Show a => a -> String.
DJG

Odpowiedzi:

16

Jak dotąd odpowiedź jest myląca.

Należy wprowadzić rozróżnienie między polimorfizmem „parametrycznym” a „przeciążeniem ad hoc”. Parametryczny oznacza „zachowuje się jednakowo dla wszystkich typów a”, podczas gdy „ad-hoc” - co Simon nazywa polimorficznym - zmienia implementację w zależności od typu.

Przykładami obu są reverse :: [a] -> [a], które są parametryczne i show :: Show a => a -> Stringktóre są „przeładowane ad-hoc”.

Jeśli chcesz bardziej abstrakcyjnej intuicji, myślę, że warto rozważyć klasy czasowników w języku naturalnym, które „działają” na wszystkie obiekty, takie jak „posiadać” lub „myśleć”, które nie stanowią ograniczeń dla obiektu, ale „ otwierać ”wymaga tego, o czym mówimy, można otworzyć. Mogę „myśleć o drzwiach” i „otwierać drzwi”, podczas gdy nie ma sensu np. „Otwierać drzewa”. Idąc dalej za przykładem „otwarcie” to „polimorficzne ad-hoc” jako „otwarcie okna” i „otwarcie biletu reklamacyjnego z obsługą klienta” to dwie bardzo różne rzeczy. Jeśli wydaje się to wymuszone - zapomnij! Mi to pasuje.

Oba są jednak rozwiązywane w czasie kompilacji i w rzeczywistości „kasowane”. Modulo różne rozszerzenia GHC i szablon Haskell itp. W rzeczywistości typy kasowane podczas kompilacji i nigdy nie są sprawdzane w czasie wykonywania.

Funkcje parametrycznie polimorficzne zachowują się identycznie dla wszystkich typów, więc należy wygenerować tylko jeden fragment kodu, podczas gdy kompilator decyduje w czasie kompilacji, która wersja funkcji „klasy” powinna być uruchomiona w danym punkcie programu. Z tego powodu istnieje ograniczenie jednej instancji dla typu dla każdej klasy typu i odpowiedniego obejścia „nowego typu”.

Implementacja została szczegółowo opisana w podręczniku SPJ oraz papierze Wadlera i Blotta na temat klas typów .

Kris
źródło
Czy uważasz, że powinienem usunąć swoją odpowiedź?
Simon Bergot,
Nie, w porządku jest twoje ostrzeżenie, że nie trafisz dokładnie w słownictwo
:)
Czy możesz trochę wyjaśnić, dlaczego GHC może usuwać typy? Czy to dzięki głównemu pisaniu?
Simon Bergot,
2
Zasadniczo w czasie wykonywania albo parametrycznie polimorficzne funkcje mogą istnieć tylko raz i wywoływać funkcje polimorficzne ad-hoc za pomocą jakiejś wirtualnej metody wysyłki lub cały kod może być generowany dla każdego typu osobno i wywołania statycznie powiązane. Każda implementacja jest poprawna z językowego punktu widzenia (zauważ, że Haskell nie ma typów polimorficznych; coś takiego można stworzyć tylko z forallrozszerzeniem GHC ).
Jan Hudec
Czy istnieje jakieś rozszerzenie GHC, które nie pozwala na usunięcie typów? Przeciążenie jest statyczne i bez całkowicie zależnych typów nie mogę myśleć o niczym
Daniel Gratzer
1

ostrzeżenie: moje doświadczenie w CS nie jest zbyt mocne, więc nie zawsze używam właściwego słownictwa, a w niektórych punktach mogę się mylić. W każdym razie oto moje rozumienie:

Myślę, że mylisz leki generyczne z polimorfizmem.

Typy ogólne, takie jak List<Foo>używane są do opisywania typów, które przyjmują inne typy jako parametry i umożliwiają bogatsze sprawdzanie typów.

Ogólną funkcją w haskell może być count:: List a -> Int. Przyjmuje listy dowolnego typu i zwraca liczbę elementów. Jest tylko jedna implementacja.

Zwykle podczas definiowania listy nie można niczego zakładać o T. Można go tylko przechowywać i oddawać.

Twoja to_stringfunkcja jest funkcją polimorficzną, co oznacza, że ​​będzie zachowywać się inaczej w różnych okolicznościach. W haskell odbywa się to za pomocą klas, które działają jak przymiotniki dla typów.

Masz Showklasę, która definiuje show :: a -> Stringfunkcję.

Gdy typ Fooimplementuje Showklasę, musi podać definicję show. Tego typu można następnie użyć w funkcjach wymagających Showkwalifikatora (jak w Show a => a -> whatever). Haskell nie może usuwać typów, ponieważ te funkcje muszą znaleźć poprawną implementację showfunkcji.

Simon Bergot
źródło
We wspólnym seplenie funkcje polimorficzne nazywane są „funkcjami ogólnymi” IIRC i użyłem tego samego (mylącego) słownictwa. Twoja odpowiedź jest przydatna, a ostatni argument dość przekonujący. .-)
user40989
„Jest tylko jedna implementacja” - oczywiście tylko jedna, która ma sens, ale jest nieskończenie wiele możliwych. Funkcja typu a → b ma | b | ^ | a | możliwe implementacje (rozważ liczbę funkcji typu Bool → Bool), a listy nie mają górnego limitu wielkości.
Jon Purdy