Подтвердить что ты не робот

Перегружается ли Haskell перегрузкой типа?

Основываясь на том, что я прочитал о Haskell, и эксперименте, который я провел с GHC, кажется, что Haskell имеет перегрузку типа возвращаемого типа (так называемый ad hoc полиморфизм). Одним из примеров этого является функция fromInteger, которая может дать вам Double или Integer в зависимости от того, где используется результат. Например:

fd :: Double -> String
fd x = "Double"

fi :: Integer -> String
fi x = "Integer"

fd (fromInteger 5)  -- returns "Double"
fi (fromInteger 5)  -- returns "Integer"

Нежное введение в Haskell, похоже, соглашается с этим, когда говорится:

Тип полиморфизма, о котором мы говорили до сих пор, обычно называют параметрическим полиморфизмом. Существует еще один вид, называемый ad hoc-полиморфизм, более известный как перегрузка. Вот несколько примеров ad hoc-полиморфизма:

  • Литералы 1, 2 и т.д. часто используются для представления как фиксированных, так и произвольных целых чисел точности.

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

И на самом деле, я нашел несколько ответов на другие вопросы о переполнении стека, которые предполагают, что Haskell имеет перегрузку по типу возврата.

Однако, по крайней мере один программист Haskell сказал мне, что это не перегрузка возвращаемого типа, а вместо этого является примером "параметрического полиморфизма, где параметр связан универсальным квантором".

Я думаю, что он получает то, что fromInteger возвращает значение из каждого экземпляра Num (своего рода недетерминированный тип).

Это кажется разумной интерпретацией, но, насколько я могу судить, Haskell никогда не позволяет нам смотреть на более чем одно из этих значений экземпляров (частично благодаря Ограничение мономорфизма). Также кажется, что фактический экземпляр, значение которого мы смотрим, можно определить статически. Из-за всего этого представляется разумным сказать, что в выражении fd (fromInteger 5) подвыражение fromInteger 5 имеет тип Double, тогда как в выражении fi (fromInteger 5) подвыражение fromInteger 5 имеет тип Integer.

Итак, имеет ли Haskell перегрузку типа возвращаемого типа?

Если нет, укажите пример одного из следующих действий:

  • действительный код Haskell, который имел бы другое поведение, если Haskell возвращал тип перегрузки
  • действительный код Haskell, который был бы недопустимым, если Haskell возвращал тип перегрузки
  • недопустимый код Haskell, который был бы действителен, если Haskell возвращал тип перегрузки
4b9b3361

ОТВЕТЫ

Ответ 1

Ну, один из способов взглянуть на это - это то, что Haskell переводит полиморфизм возвращаемого типа, о котором вы думаете, в параметрический полиморфизм, используя что-то, называемое переводящим словаря перевод для классов типов. (Хотя это не единственный способ реализовать классы типов или причины о них, он просто самый популярный.)

В принципе, fromInteger имеет этот тип в Haskell:

fromInteger :: Num a => Integer -> a

Это может быть переведено внутренне во что-то вроде этого:

fromInteger# :: NumDictionary# a -> Integer -> a
fromInteger# NumDictionary# { fromInteger = method } x = method x

data NumDictionary# a = NumDictionary# { ...
                                       , fromInteger :: Integer -> a
                                       , ... }

Итак, для каждого конкретного типа T с экземпляром Num существует значение NumDictionary# T, которое содержит функцию fromInteger :: Integer -> T, и весь код, который использует класс типа Num, преобразуется в код, который принимает словарь как аргумент.

Ответ 2

Я хотел бы затронуть одну небольшую часть вашего вопроса:

Также кажется, что фактический экземпляр, значение которого мы смотрим, можно определить статически.

Это не очень точно. Рассмотрим следующий нечеткий тип данных:

data PerfectlyBalancedTree a
    = Leaf a
    | Branch (PerfectlyBalancedTree (a,a))
    deriving (Eq, Ord, Show, Read)

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

Leaf 0
Branch (Leaf (0, 0))
Branch (Branch (Leaf ((0,0),(0,0))))
Branch (Branch (Branch (Leaf (((0,0),(0,0)),((0,0),(0,0))))))

Фактически вы можете визуализировать любое значение этого типа как начальную последовательность тегов n Branch, за которой следует тэг "мы наконец-то сделали, спасибо доброте" Leaf, за которым следует 2 ^ n-кортеж содержащегося типа. Круто.

Теперь мы собираемся написать функцию для анализа более удобного для них представления. Вот несколько примеров:

*Main> :t fromString
fromString :: String -> PerfectlyBalancedTree Integer
*Main> fromString "0"
Leaf 0
*Main> fromString "b(42,69)"
Branch (Leaf (42,69))
*Main> fromString "bbb(((0,0),(0,0)),((0,0),(0,0)))"
Branch (Branch (Branch (Leaf (((0,0),(0,0)),((0,0),(0,0))))))

Вдоль пути будет удобно написать немного более полиморфную функцию. Вот он:

fromString' :: Read a => String -> PerfectlyBalancedTree a
fromString' ('b':rest) = Branch (fromString' rest)
fromString' leaf = Leaf (read leaf)

Теперь наша реальная функция - это одно и то же с другой сигнатурой типа:

fromString :: String -> PerfectlyBalancedTree Integer
fromString = fromString'

Но подождите секунду... что только что произошло? Я что-то пропустил тебе много раз! Почему мы просто не писали это напрямую?

fromStringNoGood :: String -> PerfectlyBalancedTree Integer
fromStringNoGood ('b':rest) = Branch (fromStringNoGood rest)
fromStringNoGood leaf = Leaf (read leaf)

Причина в том, что в рекурсивном вызове fromStringNoGood имеет другой тип. Он не вызван, чтобы вернуть a PerfectlyBalancedTree Integer, на который вызывается return PerfectlyBalancedTree (Integer, Integer). Мы могли бы написать такую ​​функцию...

fromStringStillNoGood :: String -> PerfectlyBalancedTree Integer
fromStringStillNoGood ('b':rest) = Branch (helper rest)
fromStringStillNoGood leaf = Leaf (read leaf)

helper :: String -> PerfectlyBalancedTree (Integer, Integer)
helper ('b':rest) = Branch ({- ... what goes here, now? -})
helper leaf = Leaf (read leaf)

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

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

Ответ 3

Основная статья о стилях типа Haskell называется "Как сделать ad-hoc полиморфизм менее ad hoc" . Итак, ответ на ваш вопрос - это квалифицированное "да" - в зависимости от того, как ad hoc вам требуется перегрузка типа возвращаемого типа...

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

Ответ 4

Вы правы: у Haskell есть перегрузка, и он обеспечивает его через свой механизм типа.

Рассмотрим следующие сигнатуры:

f :: [a] -> a
g :: Num a => [a] -> a

Первая подпись сообщает вам, что при задании списка элементов любого типа a, f будет выдаваться значение типа a. Это означает, что реализация f не может делать никаких предположений о типе a и о том, какие операции он допускает. Это пример параметрического полиморфизма. Моментное отражение показывает, что на самом деле очень мало вариантов реализации f: единственное, что вы можете сделать, это выбрать элемент из предоставленного списка. Концептуально существует одна общая реализация f, которая работает для всех типов a.

Вторые подписи говорят вам, что при задании списка элементов некоторого типа a, принадлежащего типу класса Num, g будет выдавать значение этого типа a. Это означает, что реализация g может потреблять, производить и манипулировать значениями типа a, используя все операции, входящие в класс типа Num. Например, g может добавлять или умножать элементы списка, выбирать минимальный список, возвращать поднятую константу,... Это пример перегрузки, который обычно используется для быть формой ad-hoc-полиморфизма (другой основной формой является принуждение). Концептуально существует различная реализация для g для всех типов a в Num.

Ответ 5

Он имеет перегрузку типа возвращаемого типа. Для хорошего примера см. Функцию "Чтение". Он имеет тип Read a = > String → a. Он может читать и возвращать все, что реализует класс типа чтения.