Параметрический полиморфизм против Ad-hoc-полиморфизма

Ответ 1

В соответствии с TAPL, §23.2:

Параметрический полиморфизм (...) позволяет использовать один кусок код, который будет набираться "в общем", используя переменные вместо фактических типов и затем создается экземпляр с определенными типами по мере необходимости. Параметрические определения одинаковы: все их экземпляры ведут себя одинаково. (...)

Ad-hoc-полиморфизм, напротив, позволяет проявлять полиморфную ценность различное поведение при "просмотре" на разных типах. Самый распространенный примером ad-hoc-полиморфизма является перегрузка, которая связывает одно символ функции со многими реализациями; компилятор (или система времени выполнения, в зависимости от того, является ли перегрузочное разрешение статическим или динамическим) выбирает соответствующую реализацию для каждого приложения функция, основанная на типах аргументов.

Итак, если вы рассматриваете последовательные этапы истории, то нетрадиционная официальная Java (aka pre- J2SE 5.0, bef. sept., 2004) имел ad-hoc-полиморфизм, поэтому вы могли перегрузить метод - но не параметрический полиморфизм, поэтому вы не могли напишите общий метод. Впоследствии вы могли бы обойти оба, конечно.

Для сравнения, с самого начала в 1990 году, Haskell был параметрически полиморфным, то есть вы могли написать:

swap :: (A; B) -> (B; A)
swap (x; y) = (y; x)

где A и B являются переменными типа, могут быть созданы для всех типов без предположений.

Но не существовало ранее существовавшей конструкции, дающей ad-hoc-полиморфизм, который намеревается позволить вам писать функции, которые применяются к нескольким, но не ко всем типам. Типовые классы были реализованы как способ достижения этой цели.

Они позволяют вам описывать класс (что-то похожее на интерфейс Java), предоставляя подпись типа функций, которые вы хотите реализовать для вашего общего типа. Затем вы можете зарегистрировать некоторые (и, надеюсь, несколько) экземпляры, соответствующие этому классу. Тем временем вы можете написать общий метод, например:

between :: (Ord a)  a -> a -> a -> Bool
between x y z = x ≤ y ^ y ≤ z

где Ord - это класс, определяющий функцию (_ ≤ _). При использовании (between "abc" "d" "ghi") статически ставится, чтобы выбрать правильный экземпляр для строк (а не целых чисел) - точно в тот момент, когда перегрузка метода (Java) была бы такой.

Вы можете сделать что-то подобное на Java с ограниченными подстановочными знаками. Но ключевое различие между Haskell и Java на этом фронте состоит в том, что только Haskell может автоматически выполнять автоматический перевод словаря: на обоих языках, учитывая два экземпляра Ord T, скажем b0 и b1, вы может построить функцию f, которая принимает их как аргументы и создает экземпляр для типа пары (b0, b1), используя, скажем, лексикографический порядок. Скажите теперь, что вам дано (("hello", 2), ((3, "hi"), 5)). В Java вам нужно запомнить экземпляры для string и int и передать правильный экземпляр (сделанный из четырех приложений f!), Чтобы применить between к этому объекту. Haskell может применять compositionality и выяснить, как построить правильный экземпляр, заданный только для наземных экземпляров и конструктора f (это распространяется на другие конструкторы, конечно).

Теперь, что касается вывода типа (и, вероятно, это должен быть отдельный вопрос), для обоих языков он неполный, в том смысле, что вы всегда можете написать программу un-annotated для которые компилятор не сможет определить тип.

• для Haskell, это потому, что он impredicative (a.k.a. первоклассный) полиморфизм, для которого вывод типа неразрешимый. Обратите внимание, что в этой точке Java ограничивается полиморфизмом первого порядка (что-то, на котором расширяется Scala).

• для Java, потому что он поддерживает контравариантный подтипирование.

Но эти языки в основном отличаются в диапазоне программных операторов, к которым применяется метод вывода типа, и в важности, заданной правильности результатов вывода типа.

• Для Haskell вывод применяется ко всем "не очень полиморфным" терминам и прилагает серьезные усилия для возвращения результатов звука на основе опубликованных расширений известного алгоритма:

  • По сути, вывод Haskell основан на Hindley-Milner, который дает вам полные результаты, как только при выводе типа приложения переменные типа (например, A и B в приведенном выше примере) могут быть созданы только с использованием не полиморфных типов (я упрощаю, но это, по сути, полиморфизм ML-стиля, который вы можете найти, например, Ocaml.).
  • недавний GHC удостоверится, что может потребоваться аннотация типа только для let-binding или λ-абстракции, которая имеет тип не-Damas-Milner.
  • Haskell попытался оставаться относительно близким к этому неопровержимому ядру даже на самых волосатых расширениях (например, GADT). Во всяком случае, предлагаемые расширения почти всегда появляются в документе с доказательством правильности вывода расширенного типа.

• Для Java вывод типа применяется в гораздо более ограниченном режиме:

  До выпуска Java 5 не было вывода типа в Java. Согласно языковой культуре Java, тип каждой переменной, метода и динамически выделенного объекта должен быть явно объявлен программистом. Когда generics (классы и методы, параметризованные по типу) были введены в Java 5, , язык сохранил это требование для переменных, методов и распределений. Но введение полиморфных методов (параметризованных по типу) диктует, что либо (i) программист предоставляет аргументы типа метода на каждом сайте вызова полиморфного метода, либо (ii) язык поддерживает вывод аргументов типа метода. Чтобы избежать создания дополнительной канцелярской нагрузки для программистов, разработчики Java 5 решили выполнить вывод типа для определения аргументов типа для вызовов полиморфных методов. (источник, акцент мой)

  алгоритм вывода по существу того, что GJ, но с несколько kludgy добавление подстановочных знаков в качестве запоздалой мысли ( Обратите внимание, что я не обновляю возможные исправления, сделанные в J2SE 6.0). Большая концептуальная разница в подходе заключается в том, что вывод Java является локальным, в том смысле, что предполагаемый тип выражения зависит только от ограничений, генерируемых системой типов, и от типов его подвыражений, но не от контекста.

  Обратите внимание, что строка партии относительно неполного, а иногда и неправильного вывода типа относительно отложена. По спецификация:

  Обратите внимание также, что вывод типа никак не влияет на качество звука. Если выведенные типы бессмысленны, вызов вызовет ошибку типа. Алгоритм вывода типа следует рассматривать как эвристику, разработанную на практике на практике. Если он не сможет вывести желаемый результат, вместо него могут использоваться явные тип paramneters.

Ответ 2

Параметрический полиморфизм означает, что мы не заботимся о типе, мы будем реализовывать функцию одинаково для любого типа. Например, в Haskell:

length :: [a] -> Int
length [] = 0          
length (x:xs) = 1 + length xs

Нам все равно, каков тип элементов списка, мы просто заботимся о том, сколько их есть.

Ad-hoc-полиморфизм (например, перегрузка метода), однако, означает, что мы будем использовать другую реализацию в зависимости от типа параметра.

Вот пример в Haskell. Пусть говорят, что мы хотим определить функцию, называемую makeBreakfast.

Если входной параметр Eggs, я хочу, чтобы makeBreakfast возвращал сообщение о том, как делать яйца.

Если входной параметр Pancakes, я хочу, чтобы makeBreakfast возвращал сообщение о том, как сделать блины.

Мы создадим класс под названием BreakfastFood, который реализует функцию makeBreakfast. Реализация makeBreakfast будет различной в зависимости от типа ввода для makeBreakfast.

class BreakfastFood food where
  makeBreakfast :: food -> String

instance BreakfastFood Eggs where
  makeBreakfast = "First crack 'em, then fry 'em"

instance BreakfastFood Toast where
  makeBreakfast = "Put bread in the toaster until brown"

В соответствии с концепциями Джона Митчелла на языках программирования

Ключевое различие между параметрическим полиморфизмом и перегрузкой (aka ad-hoc polymorphism) заключается в том, что параметрические полиморфные функции используют один алгоритм для работы с аргументами многих разных типов, тогда как перегруженные функции могут использовать для каждого типа аргументов другой алгоритм.

Ответ 3

Полное обсуждение того, что означает параметрический полиморфизм и ad-hoc-полиморфизм, и насколько они доступны в Haskell и Java, являются длинными; однако ваши конкретные вопросы можно решить гораздо проще:

Как алгоритм вывода типа, например. в Java отличается от вывода типа в Haskell?

Насколько я знаю, Java не делает вывода типа. Поэтому разница в том, что Haskell делает это.

Пожалуйста, дайте мне пример ситуации, когда что-то может быть написано в Java/ Scala, но не может быть написано в Haskell (в соответствии с модульными особенностями этих платформ тоже) и наоборот.

Один очень простой пример того, что Haskell может сделать, что Java не может определить maxBound :: Bounded a => a. Я не знаю достаточно Java, чтобы указать на то, что он может сделать, что Haskell не может.