Может ли функция с корректным типом быть неприменимой? (Haskell) - PullRequest
7 голосов
/ 01 февраля 2020

У меня есть функция foo = \f x -> let c = \y -> x in f c, которую я нашел, чтобы найти:

\forall a,b,r. ((b -> a) -> r) -> a -> r.

GHCI подтверждает этот тип: foo :: ((p1 -> p2) -> t) -> p2 -> t

Однако я не могу найти подходящую функцию, которая соответствует этим параметрам, так что foo оценивает.

Я пытался Следующие функции не увенчались успехом:

bu :: Num a => ([Char] -> a) -> a
bu x = (x "hello") * 2 

ba :: (Fractional a1, Foldable t) => t a2 -> a1
ba x = (fromIntegral (length x) ) / 2

Другой попыткой был выбор следующих функций:

bu :: Num a => ([Char] -> a) -> a -> a
bu x = (+ ((x "hello") * 2))

ba :: (Fractional a1, Foldable t) => t a2 -> a1
ba x = (fromIntegral (length x) ) / 2

Теперь я могу позвонить (bu ba) 4 и получить правильный результат.

Я понимаю, почему они не работают. Кажется, проблема в том, что в первом аргументе (p1 -> p2) -> t), t должна быть функцией, которая принимает аргумент p2. Однако, как только мы это сделаем, тип этой функции изменится на что-то вроде (a -> a) и больше не будет корректно использоваться foo.

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

Ответы [ 2 ]

8 голосов
/ 01 февраля 2020

Вот простое доказательство того, что функция может быть неприменима (без учета дна)

data Never = Never Never

justTryIt :: Never -> ()
justTryIt _ = ()

Однако ваша функция применима

main = print $ foo (\c -> c ()) 3

Так, каков тип этой лямбды?

g :: (() -> a) -> a
g = \c -> c ()

Дело в том, что вам не нужна функция

g :: (a -> b) -> c

, которая необитаема (iGnOrInG bOtToMs). Сигнатура типа просто говорит, что вы можете взять функцию, в которой все 3 типа (например, ab c.) могут различаться. IE это работает одинаково хорошо

g :: (Int -> String) -> Bool
g f = null $ f 3

main = print $ foo g "so concrete"
5 голосов
/ 01 февраля 2020

Функция типа p1 -> p2 невозможна для записи; что в основном говорит: «учитывая любой возможный тип, я могу дать вам любой другой возможный тип». Удачи с этим!

Тип (p1 -> p2) -> t невозможен по той же причине. Тем не менее, (p1 -> p2) -> Bool вполне возможно:

f :: (p1 -> p2) -> Bool
f x = True

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

В общем, любая реализуемая функция может быть успешно вызванным? Это интересный вопрос. Я не уверен, что ответ. Я хотел бы знать!

РЕДАКТИРОВАТЬ: Подумайте об этом ... сигнатура типа каждой реализуемой функции может быть интерпретирована как теория (и реализация функции в некотором смысле является «доказательством» этой теории). Функция, которая принимает другую функцию в качестве входных данных, похожа на «этот теорум верен, если этот другой теорем верен». Так что, если вы можете придумать доказательство того, что «X истинно, если Y истинно», где Y определенно ложно ... тогда у вас есть реализуемая функция, которая никогда не может быть вызвана.

Все это весело игнорирует тот факт, что настоящий Haskell имеет несколько способов сломать систему типов и обойти эти хорошие результаты. Например, функция error "banana" имеет тип a (т. Е. любой возможный тип ). Таким образом, в этом «обманном» смысле все функции Haskell могут быть вызваны.

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