Почему эти две функции в Haskell имеют одинаковый тип?

Question

Я работаю с Программированием Грэма Хаттона на Хаскеле , и в главе 3 задается вопрос "Что это за тип?"для функции twice f x = f (f x).

Мне кажется, я понимаю, почему ответ twice :: (t -> t) -> t -> t.( Редактировать : я не понимаю, почему. Смотрите мой комментарий к ответу Паоло.) Однако для эксперимента я написал другую функцию thrice f x = f (f (f x)).

Что я определенно не понимаю, почему thrice также имеет тип thrice :: (t -> t) -> t -> t.

Они работают так, как я ожидал (см. Ниже), но я не понимаю, кактип thrice имеет смысл.

с ghci:

>> twice tail [0,1,2,3,4]
[2,3,4]
>> thrice tail [0,1,2,3,4]
[3,4]

Answer 1

Возможно, это проще увидеть без очков:

twice f = f . f
thrice f = f . f . f

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

f :: a -> r     -- argument type -> result type

, условие пригодности означает, что r должно соответствовать a.Для переменных типа это означает r = a.Таким образом, twice, а также thrice переводят функцию из некоторого типа в один и тот же тип и возвращают функцию из этого типа в тот же тип,

twice :: (a -> a) -> (a -> a)
thrice :: (a -> a) -> (a -> a)

Поскольку стрелка типа функции является ассоциативно правой(x -> y -> z = x -> (y -> z), последние скобки в типе могут быть опущены.

Answer 2

Тип double указывает, что double является функцией от функции с доменом a и codomain a для функции с домен a и кодомен a . Тип трижды указывает, что трижды является функцией от функции с доменом a и codomain a до функции с доменом a и кодомен a .

Чтобы понять почему, рассмотрим производную типа дважды и трижды . Дана функция f : a → a и переменная x , правило для определения типа f ( fx ) утверждает, что мы должны сначала определить типы f и (fx) , а затем применить правило для применения функции. Правило для определения типа (fx) гласит, что сначала мы должны определить тип f и x , а затем применить правило для применения функции.

Во-первых, поскольку f имеет тип a → a и x имеет тип a , правило для приложения функции говорится, что ( fx ) имеет тип a . Поскольку f имеет тип a → a и ( fx ) имеет тип a , правило для применения функции утверждает, что f ( fx ) имеет тип a . Дополнительное применение правила для применения функции дает f ( f ( f x )) типа a . Как видите, повторное применение правила для приложения дает f ⁿ x будет иметь тип a для всех n ∈ ℕ.

Во-вторых, правило для абстракции функции гласит, что если x : τ , M : τ ' и x не встречается свободно в M , тогда абстракция λ x : τ . M имеет тип τ → τ '. У нас есть термины f ( fx ) и f ( f ( fx )) оба типа a и переменная x с типом a . Следовательно, абстракции λ x : a . f ( f x ) и λ x : a . f ( f ( f x )) оба имеют тип a → a . Наконец, поскольку f : a → a , применение правила для абстракции функции еще раз дает λ f : a → a . λ x : a . f ( f x ) и λ f : a → a . λ x : a . f ( f ( fx )) имеют тип ( a → a ) → ( a → a ).

Как видите, система типов Хаскелла слишком невыразительна, чтобы утверждать, что дважды применяет функцию f к аргументу x два раза, тогда как трижды применяет функцию f к аргументу x три раза. может выразить то, что дважды и трижды принимают функцию в качестве входных данных и возвращают функцию из термина x в термин y оба типа a . Эта функция является λ x : a . f ( f x ) для дважды и λ x : a . f ( f ( f x )) для трижды .

Я бы предложил прочитать краткое введение в полиморфное λ-исчисление, на котором основана система типов Хаскелла. Это представит отношение типов и, вероятно, поможет читателю доказать, что определенные термины имеют определенные типы.

Answer 3

Извините, может быть, я не понимаю ваш вопрос, но если вы посмотрите на свой собственный пример со списком, вы увидите, что как в два раза, так и в три раза, входные данные являются функцией от списка к списку (tail) и список ([0,1,2,3,4]), а тип возвращаемого значения - список.

Таким образом, twice и thrice соответствуют сигнатуре (t -> t) -> t -> t: функция от t до t (в вашем случае tail), at (в вашем случае список) и еще один t (список) взамен

Answer 4

В попытке выиграть конкурс краткости:

Сигнатуры типов задают типы для входных данных (аргументов) функции и для значения, которое возвращает функция.
Таким образом, количество элементов в сигнатуре типа функции равно (n + 1), где n - количество аргументов, которые принимает функция.