Стираются ли типы в Haskell?

13

У Haskell есть понятие «универсальных функций», которое имеет некоторое очевидное сходство с обычным языком - не имея опыта работы с Haskell или с обычным языком, я могу быть здесь весьма приблизительным. Это означает, что можно определить универсальное to_stringсредство для определения строкового представления для всех типов. Конечно, средство должно быть определено в особых случаях, но есть to_stringфункция, чья подпись α → string.

Стираются ли типы в Haskell, как в OCaml? Если да, то как реализация «универсальных функций» в Haskell отличается от реализации общего lisp, где типы являются динамическими и, следовательно, не стираются?

Я понимаю, что детали реализации зависят от компилятора, но, вероятно, есть положения, общие для многих или всех реализаций.

user40989
источник
5
Помните, что вы, вероятно, не можете определить нетривиальную функцию типа a -> String. Скорее всего, у вас будет ограничение типа Show a => a -> String.
DJG

Ответы:

16

Ответ пока вводит в заблуждение.

Необходимо проводить различие между «параметрическим» и «специальным перегрузочным» полиморфизмом. Параметрический означает «ведет себя единообразно для всех типов a», тогда как «ad-hoc» - то, что Саймон называет полиморфным - меняет реализацию на основе типа.

Примерами того reverse :: [a] -> [a], что является параметрическим и show :: Show a => a -> Stringперегруженным.

Если вам нужна более абстрактная интуиция, я думаю, что это помогает рассмотреть классы глаголов естественного языка, которые «работают» для всех объектов, например «владеть» или «думать», которые не создают никаких ограничений для объекта, но « «открыть» требует того, о чем мы говорим, можно открыть. Я могу «думать о двери» и «открывать дверь», хотя нет смысла, например, «открывать дерево». Если взять еще один пример, то «открыть» - это «специальная полиморфность», как «открыть окно» и «открыть билет-жалобу через службу поддержки» - это две совершенно разные вещи. Если это кажется вынужденным - забудь об этом! Меня устраивает.

Однако оба они разрешаются во время компиляции и фактически «стираются». Модульные различные расширения GHC и Template Haskell и т.д. Типы будут фактически стерты во время компиляции и никогда не проверяются на время выполнения.

Параметрически полиморфные функции ведут себя одинаково для всех типов, поэтому необходимо сгенерировать только один фрагмент кода, в то время как компилятор решает во время компиляции, какую версию функции с классификацией типов следует запускать в конкретной программной точке. По этой же причине существует ограничение по одному экземпляру на тип для каждого класса типов и соответствующий обходной путь «нового типа».

Реализация подробно описана в учебнике SPJ и в Wadler and Blotts о классах типов .

Kris
источник
Как вы думаете, я должен удалить свой ответ?
Саймон Бергот
Нет, это нормально с предупреждением не ударять точный словарь:)
Kris
Не могли бы вы немного рассказать, почему GHC может стирать типы? Это благодаря основной типизации?
Саймон Бергот
2
В общем случае во время выполнения либо параметрически полиморфные функции могут существовать только один раз и вызывать специальные полиморфные функции через некоторый метод виртуальной диспетчеризации, либо весь код может быть сгенерирован для каждого типа отдельно и вызывает статически связанные вызовы. Любая реализация верна с языковой точки зрения (обратите внимание, что Haskell не имеет полиморфных типов; такая вещь может быть создана только с forallрасширением GHC ).
Ян Худек
Существуют ли какие-либо расширения GHC, которые не позволяют удалять типы? Перегрузка является статической, и без полностью зависимых типов я ни о чем не могу думать
Даниэль Гратцер
1

предупреждение: мой опыт в CS не очень сильный, поэтому я не всегда могу использовать правильный словарный запас, и в некоторых моментах я могу ошибаться. Во всяком случае, вот мое понимание:

Я думаю, что вы путаете дженерики с полиморфизмом.

Универсальные типы, такие как List<Foo>, используются для описания типов, которые принимают другие типы в качестве параметров и позволяют более богатую проверку типов.

Общей функцией в haskell может быть count:: List a -> Int. Он принимает списки любого типа и возвращает количество элементов. Есть только одна реализация.

Обычно, определяя List, вы не можете предполагать что-либо о T. Вы можете только сохранить его и вернуть обратно.

Ваша to_stringфункция является полиморфной функцией, что означает, что она будет вести себя по-разному при разных обстоятельствах. В haskell это делается с помощью классов типов, которые работают как прилагательные для типов.

У вас есть Showкласс типов, который определяет show :: a -> Stringфункцию.

Когда тип Fooреализует Showкласс типов, он должен предоставить определение show. Этот тип может затем использоваться в функциях, требующих Showквалификатор (как в Show a => a -> whatever). Haskell не может стереть типы, так как эти функции должны найти правильную реализацию showфункции.

Саймон Бергот
источник
В общих чертах, полиморфные функции называются «универсальными функциями» IIRC, и я использовал один и тот же (запутанный) словарь. Ваш ответ полезен, а ваш последний аргумент довольно убедителен. .-)
user40989
«Есть только одна реализация» - только та, которая имеет смысл, конечно, но существует бесконечно много возможных. Функция типа a → b имеет | b | ^ | a | возможные реализации (рассмотрим количество функций типа Bool → Bool), а списки не имеют верхнего предела размера.
Джон Перди