Расчет типов функций Haskell

Question

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

Я понимаю основы, такие как:

• ие = х :: т -> т
• Kxy = х :: гр -> t1 -> т

Но возникли проблемы на более сложные вопросы, такие как:

• два FX = F (Fx)
• sxyz = x z (y z)

Любые объяснения были бы высоко оценены!

Answer 1

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

two f x = f(f(x)) 
s x y z = x(z)(y(z)) 

---

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

two :: a -> b -> c 

Мы также знаем, что переменная a типа выше фактически соответствует функции потому что f применяется как к x, так и к f(x).

two :: (a -> b) -> c -> d 

Поскольку f применяется к x мы знаем, что здесь a и c должны быть одинаковыми.

two :: (a -> b) -> a -> d 

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

two :: (a -> a) -> a -> b 

И, наконец, результатом вызова f является общим результатом из two так d должны также равны a

two :: (a -> a) -> a -> a 

Это использует всю информацию, содержащуюся в определении, и является наиболее общим типом, совместимым с определением two.

---

Мы можем сделать в основном тот же процесс для s. Мы знаем, что у него есть 3 аргумента

s :: a -> b -> c -> d 

Мы знаем, что первый и второй аргументы являются функциями какого-либо рода.Мы видим, что второй аргумент применяется к одному значению, а первый применяется к двум значениям.

s :: (a -> b -> c) -> (d -> e) -> f -> g 

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

s :: (a -> b -> c) -> (a -> d) -> a -> e 

Мы также знаем, что результат вызова второй функции является вторым аргументом первой функции, так b и d должны быть одинаковыми ,

s :: (a -> b -> c) -> (a -> b) -> a -> e 

Наконец, результат полностью применения первой функции является конечным результатом s так c и e такие же

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

---

Хотя это может быть много, чтобы переварить и добрый размытия, то, что нужно подчеркнуть, состоит в том, что инструменты, которые я использовал для решения этой проблемы, являются примитивными. Эффективно я вводил стрелки (->), когда я вижу, что тип был применен к некоторым значениям и, следовательно, должен быть функцией определенного количества аргументов, и я объединяю переменные типа, следуя значениям через их выражение. Это достаточные инструменты для вывода типов простых функций, таких как two и s.

Answer 2

Ваши two и s - это то, что известно как функции верхнего уровня, поскольку они принимают функции в качестве аргументов. У вас уже есть инструменты, чтобы различать их типы, вам просто нужно быть немного более абстрактными.

Если вы дали выражение:

f x 

Вы знаете тип f является a -> b с x :: a и f x :: b. Если вы видите

f (f x) 

Тогда можно сделать вывод, что тип выхода из (f x) такой же, как тип входного сигнала для f. Это означает, что a ~ b, поэтому f :: a -> a и x :: a.Если мы посмотрим на тип two, мы можем сделать вывод, что он соответствует схеме

two :: s -> t -> u 

но первый аргумент two является f, который имеет тип a -> a, поэтому мы можем подключить, что в качестве

two :: (a -> a) -> t -> u 

И x является вторым аргументом с типом a, поэтому мы можем подключить, что в

two :: (a -> a) -> a -> u 

А тип возвращаемого значения совпадает с типом возвращаемого f (f x), который имеет тип возвращаемого f, который имеет тип возвращаемого a, поэтому если мы подключи, что мы получаем окончательный тип

two :: (a -> a) -> a -> a 

---

Для s, мы можем сделать аналогичным образом. Мы начинаем с того, s следует за формой

s :: s -> t -> u -> v 

, поскольку он имеет 3 аргумента. Выражение (y z) является функциональным приложением, поэтому y должно иметь тип y :: a -> b, с z :: a. Подключив что к s:

s :: s -> (a -> b) -> a -> v 

Затем мы рассмотрим x z (y z). Так как y z :: b и z :: a, x является функцией двух аргументов, первый тип a и второго типа b с неизвестным типом возвращаемого c, поэтому мы можем подключить, что в качестве

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

Answer 3

Давайте посмотрим на

two f x = f (f x) 

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

Начиная с выражения f x. f является функцией, а его тип аргумента независимо x «s тип, так:

x :: a  -- a is a new variable 
f :: a -> b -- b is a new variable 

Эти два уравнения точно сказать, что я только что сказал в предыдущем предложении. Кроме того, мы создали переменную b которая является тип результата применения:

f x :: b 

Теперь давайте перейдем к f (f x).Таким образом, тип аргумента f должен быть тип f x, который мы знаем b, так:

f :: b -> c -- c is a new variable 
f (f x) :: c 

Но, конечно же, функция может иметь только один тип, и у нас уже есть тип для f :

f :: a -> b -- from above 

Это означает, что

a = b 
b = c 

Мы достигли выражения верхнего уровня в настоящее время. Итак, теперь давайте посмотрим на типы входных переменных мы нашли вместе с выражением:

f :: a -> b 
x :: a 
f (f x) :: c 

Теперь мы идем подставляя вокруг столько, сколько мы можем, выражая его с наименьшим количеством переменных, как это возможно (но только с помощью равенства, которые мы вывели). Мы постараемся сделать все это с точки зрения a.

f :: a -> b 
    = a -> a -- because b = a 
x :: a 
f (f x) :: c 
     = b -- because c = b 
     = a -- because b = a 

И там у нас есть это:

two :: (a -> a) -> a  ->  a 
     ^^^^^^^^^  ^^^^^^^^^ ^^^^^^^^^^^^^^ 
     type of f  type of x type of result 

Это более многословен, чем это необходимо, потому что я повторил себе много, чтобы вы могли видеть рассуждения участие. Существует методический способ сделать это, но я предпочитаю делать это больше как математика, продвигаясь и обнаруживая, что могу. Методический способ, как правило, заставляет меня потеряться в море переменных (что достаточно легко для компьютера, но тяжело для моего смертного человеческого мозга).

Надеюсь, это помогло.