Какое оправдание для типа fx = fx в Haskell есть? - PullRequest
4 голосов
/ 31 января 2011

Haskell дает f x = f x тип t1 -> t, но кто-нибудь может объяснить, почему?

И возможно ли, чтобы любая другая неэквивалентная функция имела такой же тип?

Ответы [ 2 ]

16 голосов
/ 31 января 2011

Хорошо, начиная с определения функции f x = f x, давайте пройдемся и посмотрим, что мы можем сделать о типе f.

Начните с совершенно неопределенной переменной типа, a. Можем ли мы вывести больше, чем это? Да, мы наблюдаем, что f - это функция, принимающая один аргумент, поэтому мы можем изменить a на функцию между двумя переменными неизвестного типа, которую мы назовем b -> c. Независимо от того, какой тип b обозначает тип аргумента x, а любой тип c должен быть типом правой части определения.

Что мы можем понять о правой стороне? Ну, у нас есть f, который является рекурсивной ссылкой на функцию, которую мы определяем, так что ее тип по-прежнему b -> c, где переменные обоих типов такие же, как и для определения f. У нас также есть x, который является переменной, связанной с определением f, и имеет тип b. Применение проверок типа f к x, поскольку они используют один и тот же неизвестный тип b, и в результате получается c.

На этом этапе все сходится, и без каких-либо других ограничений мы можем сделать переменные типа «официальными», что приведет к окончательному типу b -> c, где обе переменные являются обычными, неявно универсально определенными количественными переменными типа в Haskell.

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

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

Еще более прямой вариант - полностью удалить аргумент:

foo :: a
foo = foo

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

7 голосов
/ 31 января 2011
f x = undefined

имеет (альфа) эквивалентный тип f :: t -> a.


Если вам интересно, система типов Хаскелла получена из Хиндли-Милнера .Неофициально проверка типов начинается с наиболее разрешающих типов для всего и объединяет различные ограничения до тех пор, пока то, что остается, не будет согласованным (или нет).В этом случае наиболее общий тип - f :: t1 -> t, и нет никаких дополнительных ограничений.

Сравните с

f x = f (f x)

, который имеет тип вывода f :: t -> t, из-за объединения типоваргумент f на LHS и аргумент для внешнего f на RHS.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...