Объясните тип подписей для функций высокого порядка?

Question

function :: (t2 -> t1) -> (t1 -> t) -> t2 -> t 
function f1 f2 x = f2 (f1 x) 

function1 :: (t -> t) -> t -> t 
function1 f1 x = f1 (f1 x) 

---

function11 :: (t1 -> t1) -> t -> t1 -> t1 
function11 f1 f2 x = f1 (f1 x) 

function3 :: (t1 -> t1) -> t -> t1 -> t1 
function3 f1 f2 x = f1 (f1 (f1 x)) 

function4 :: (t1 -> t1) -> t -> t1 -> t1 
function4 f1 f2 x = f1 (f1 (f1 x)) 

Может кто-нибудь объяснить подписи типа для первых двух, а также почему тип подписи за последние 3 одинаковы? Я читаю о функциях высокого порядка, и то, что они есть, не попало мне в голову.

Answer 1

Может ли кто-нибудь объяснить типу подписи для первых двух?

Давайте дадим немного более человечно читаемые имена для переменных типа.

function :: (in -> tmp) -> (tmp -> out) -> in -> out 
function f1 f2 x = f2 (f1 x) 

Этот тип говорит: если вы дадите мне функцию, которая munges входы во временные значения, а функцию, которая munges временных значений в выходные, я дам вам обратно функцию, которая munges входы в выходы. Вы можете представить себе «конвейер обработки данных», где у нас есть множество объектов разных типов, а также операции, которые преобразуют значения одного типа в значения другого типа. Например, вот как я мог бы визуально сделать ваш function:

in ----- f1 -----> tmp ----- f2 -----> out 
    \            ^
    \           /
    `------------- function f1 f2 --------------' 

Намеченный интерпретация здесь является то, что вы можете себе представить, взяв два маршрута в этом трубопроводе - либо вы первый операция использование f1, а затем использовать операцию f2; или вы можете использовать операцию function f1 f2, чтобы сделать все это за один раз.

function1 :: (t -> t) -> t -> t 
function1 f1 x = f1 (f1 x) 

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

t ----- f1 -----> t ----- f1 -----> t 
\           ^
    \           /
    `------------- function1 f1 --------------' 

Почему тип подписи за последние 3 то же самое?

Давайте быстро освежить нашу память об определениях последних трех функций:

function2 f1 f2 x = f1 (f1 x) 
function3 f1 f2 x = f1 (f1 (f1 x)) 
function4 f1 f2 x = f1 (f1 (f1 x)) 

Хорошо, так что первый интересная вещь о function2, function3 и function4 является то, что они принимают три аргумента, f1, f2 и x, но каждый из них полностью игнорирует f2 - он никогда не упоминается в правой части = для любого из них. Во-вторых, function3 и function4 определены точно так же, поэтому неудивительно, что им может быть присвоен один и тот же тип.

Принимая эти две вещи во внимание, мы можем сузить вопрос несколько, так что мы спрашиваем, почему эти две функции имеют тип подписи:

function2' f x = f (f x) 
function3' f x = f (f (f x)) 

В частности, их общий тип подписи заключается в следующем:

(t -> t) -> (t -> t) 

Как мы уже говорили выше для function1, это означает, что они принимают на преобразование t с, и они также случиться, чтобы произвести преобразование на t с. Еще раз подумав о конвейерах обработки данных, теперь должно быть довольно понятно, почему они имеют один и тот же тип: не имеет значения, применяем ли мы нашу функцию f два раза или три внутри трубы; тип просто не меняется:

.------------------------ function3' f ------------------------. 
/                \ 
/                v 
t ----- f -----> t ----- f -----> t ----- f -----> t 
\           ^
    \          /
    `------------ function2' f -------------' 

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

Answer 2

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

В вашем первом случае функция с именем function принимает две функции типа (t2 -> t1) и (t1 -> t) и значение типа t2. Вы можете играть с ghci, чтобы получить лучшее inituition того, что он делает:

λ> :t id 
id :: a -> a 
λ> id 3 
3 
λ> function id id 3 
3 
λ> function id (\x -> x + 3) 3 
6 
λ> function (\x -> x + 3) (\x -> x + 3) 3 
9 

В вашей function1 вы берете одну функцию и значение типа t как вход.

Почему подпись типа для последних 3 одинакова?

Потому что они принимают тот же вход. Компилятор достаточно умен, чтобы сделать вывод о том, что второй аргумент, который вы передаете, является функцией типа t -> t1, даже если вы не указываете скобки. Я бы рекомендовал вам скопировать скобки, поскольку он значительно улучшает читаемость.

Как указывает Даниэль Вагнер, вы не используете вход f2 в своих последних трех определениях. Таким образом, вы можете даже передать ему нижнее значение, это не должно быть функцией:

λ> function4 id undefined "hello" 
"hello"