Почему две полиморфные функции более высокого порядка с эквивалентами разных типов эквивалентны по своим типам?

Ответ 1

Haskell статически типизирован, но это не значит, что это Fortran. Каждый тип должен фиксироваться во время компиляции, но не обязательно в рамках одного определения. Типы f и g полиморфны. Один из способов интерпретировать это состоит в том, что f - это не просто одна функция, а целое семейство перегруженных функций. Как (в С++)

int f (function<int(int)> g, int x) { return g(x); }
char f (function<char(char)> g, char x) { return g(x); }
double f (function<double(double)> g, double x) { return g(x); }
...

Конечно, было бы нецелесообразно создавать все эти функции, поэтому в С++ вы вместо этого напишите это как шаблон

template <typename T>
T f (function<T(T)> g, T x) { return g(x); }

... означает, что всякий раз, когда компилятор находит f, если ваш код проекта, он выяснит, что T в конкретном случае, затем создайте конкретный экземпляр шаблона (мономорфная функция, закрепленная на этом конкретном типе, как и примеры, которые я написал выше), и использовать этот конкретный экземпляр только во время выполнения.

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

Теперь параметрический полиморфизм Хаскелла немного отличается от шаблонов С++, но по крайней мере в вашем примере они равны: g - это целое семейство функций, включая экземпляр g :: (Int -> Char) -> Int -> Char (который не является совместим с типом f), но также и с g :: (Int -> Int) -> Int -> Int. Когда вы помещаете f и g в один список, компилятор автоматически понимает, что здесь подходит только подсемейство g, тип которого совместим с f.

Да, это действительно форма подтипирования. Когда мы говорим, что "Haskell не имеет подтипирования", мы имеем в виду, что любой конкретный (Rank-0) тип не пересекается со всеми другими типами Rank-0, но полиморфные типы могут перекрываться.

Ответ 2

@leftroundabout прочен; heres более технический дополнительный ответ.

В Haskell существует какое-то отношение подтипирования: отношение "общий экземпляр системы F". Это то, что использует компилятор при проверке выводимого типа функции против ее подписи. В принципе, предполагаемый тип функции должен быть, по крайней мере, полиморфным, как и его подпись:

f :: (a -> a) -> a -> a
f g x = g x

Здесь выведенный тип f равен forall a b. (a -> b) -> a -> b, так же, как и выданное вами определение g. Но подпись более ограничительна: она добавляет ограничение a ~ b (a равно b).

Haskell проверяет это, сначала заменяя переменные типа в сигнатуре переменными типа Skolem - это новые уникальные константы типа, которые объединяются только с собой (или переменными типа). Я использую обозначение $a для представления константы Сколема.

forall a. (a -> a) -> a -> a
($a -> $a) -> $a -> $a

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

Далее, компилятор выполняет проверку на добавление. Это по существу то же самое, что и обычная унификация типов, где a -> b ~ Int -> Char дает a ~ Int и b ~ Char; но из-за его отношения подтипирования, он также учитывает ковариацию и контравариантность типов функций. Если (a -> b) является подтипом (c -> d), то b должен быть подтипом d (ковариантным), но a должен быть супертипом c (контравариантным).

{-1-}(a -> b) -> {-2-}(a -> b)  <:  {-3-}($a -> $a) -> {-4-}($a -> $a)

{-3-}($a -> $a) <: {-1-}(a -> b)  -- contravariant (argument)
{-2-}(a -> b) <: {-4-}($a -> $a)  -- covariant (result)

Компилятор генерирует следующие ограничения:

$a <: a  -- contravariant
b <: $a  -- covariant
a <: $a  -- contravariant
$a <: b  -- covariant

И решает их путем объединения:

a ~ $a
b ~ $a
a ~ $a
b ~ $a

a ~ b

Таким образом, выводимый тип (a -> b) -> a -> b является по меньшей мере таким же полиморфным, как подпись (a -> a) -> a -> a.

Когда вы пишете xs = [f, g], происходит обычная унификация: у вас есть две подписи:

forall a.   (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b

Они создаются со свежими переменными типа:

(a1 -> a1) -> a1 -> a1
(a2 -> b2) -> a2 -> b2

Затем унифицирован:

(a1 -> a1) -> a1 -> a1  ~  (a2 -> b2) -> a2 -> b2
a1 -> a1  ~  a2 -> b2
a1 -> a1  ~  a2 -> b2
a1 ~ a2
a1 ~ b2

И наконец решил и обобщил:

forall a1. (a1 -> a1) -> a1 -> a1

Таким образом, тип g был менее общим, потому что он был ограничен тем же типом, что и f. Таким образом, выведенный тип xs будет [(a -> a) -> a -> a], поэтому вы получите сообщение о том же типе, пишущее [f (\x -> [x]) "foo" | f <- xs], как вы писали f (\x -> [x]) "foo"; даже если g более общий, вы скрыли часть этой общности.

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

Например, тип ($) равен (a -> b) -> a -> b; но на самом деле это более ограничительная версия id :: c -> c! Просто установите c ~ a -> b. Таким образом, на самом деле вы можете написать foo `id` (bar `id` baz quux) вместо foo $ bar $ baz quux, но эта специализированная функция идентификации дает понять компилятору, что вы ожидаете использовать его для применения функций к аргументам, чтобы он мог выручить раньше и дать вам больше описательное сообщение об ошибке, если вы допустили ошибку.