сигнатуры / типы в функциональном программировании (OCaml)

Question

Я начал изучать функциональное программирование (OCaml), но я не понимаю одну важную тему о fp: сигнатуры (я не уверен, что это правильное имя).Когда я что-то набираю и компилирую с помощью ocaml, я получаю, например:

# let inc x = x + 1 ;;
val inc : int -> int = <fun>

Это тривиально, но я не знаю, почему это:

let something f g a b = f a (g a b)

дает вывод:

val something : (’a -> ’b -> ’c) -> (’a -> ’d -> ’b) -> ’a -> ’d -> ’c = <fun>

Я полагаю, что эта тема является абсолютно базовой для fp для многих из вас, но я прошу помощи здесь, потому что я не нашел что-либо в Интернете о сигнатурахв OCaml (есть некоторые статьи о сигнатурах в Haskell, но не объяснениях).

Если эта тема каким-то образом выживет, я выкладываю здесь несколько функций, которые заставили меня запутаться:* Спасибо за помощь и объяснения.

Answer 1

Есть пара понятий, которые вам необходимо понять, чтобы понять смысл этой сигнатуры типа, и я не знаю, какие из них вы уже используете, поэтому я изо всех сил пытался объяснить каждую важную концепцию:

Curry

Как вы знаете, если у вас есть тип foo -> bar, это описывает функцию, принимающую аргумент типа foo и возвращающую результат типа bar.Поскольку -> ассоциативно справа, тип foo -> bar -> baz совпадает с foo -> (bar -> baz) и поэтому описывает функцию, принимающую аргумент типа foo и возвращающую значение типа bar -> baz, что означает, что возвращаемое значение являетсяфункция, принимающая значение типа bar и возвращающая значение типа baz.

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

Поскольку его можно вызывать вот так, функциятип foo -> bar -> baz часто называют «функцией, принимающей два аргумента», и я сделаю это в оставшейся части этого ответа.

Переменные типа

Если вы определите функцию, такую ​​как let f x = x,он будет иметь тип 'a -> 'a.Но 'a на самом деле не является типом, определенным где-либо в стандартной библиотеке OCaml, так что же это такое?

Любой тип, начинающийся с ', является так называемой переменной типа .Переменная типа может обозначать любой возможный тип.Таким образом, в приведенном выше примере f может быть вызван с int или string, или list, или чем-нибудь вообще - это не имеет значения.

Кроме того, если появляется та же переменная типав сигнатуре типа более одного раза это будет означать тот же тип.Таким образом, в приведенном выше примере это означает, что тип возвращаемого значения f совпадает с типом аргумента.Поэтому, если f вызывается с int, возвращается int.Если он вызывается с string, он возвращает string и т. Д.

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

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

Теперь, чтобы объяснить тип ...

val something : ('a -> 'b -> 'c) -> ('a -> 'd -> 'b) -> 'a -> 'd -> 'c = <fun>

Эта сигнатура типа говорит вам, что something - это функция, принимающая четыре аргумента.

Тип первого аргумента - 'a -> 'b -> 'c.Т.е. функция, принимающая два аргумента произвольного и, возможно, разных типов и возвращающая значение произвольного типа.

Тип второго аргумента - 'a -> 'd -> 'b.Это снова функция с двумя аргументами.Здесь важно отметить, что первый аргумент функции должен иметь тот же тип, что и первый аргумент первой функции, а возвращаемое значение функции должно иметь тот же тип, что и второй аргумент первой функции.

Тип третьего аргумента 'a, который также является типом первых аргументов обеих функций.

Наконец, тип четвертого аргумента 'd, который являетсятип второго аргумента второй функции.

Возвращаемое значение будет иметь тип 'c, т. е. тип возврата первой функции.

Answer 2

Если вы действительно интересуетесь предметом (и имеете доступ к университетской библиотеке), прочитайте превосходное (если несколько устарело) Уодлера «Введение в функциональное программирование». Это объясняет подписи типов и вывод типов очень красивым и читаемым способом.

Еще два совета: обратите внимание, что стрелка -> ассоциативна справа, поэтому вы можете заключить в скобки вещи справа, что иногда помогает понять вещи, то есть a -> b -> c совпадает с a -> (b -> c). Это связано со вторым намеком: функции высшего порядка. Вы можете делать такие вещи, как

let add x y = x + y
let inc = add 1

так в FP, думая о 'add' как о функции, которая должна принять два числовых параметра и возвращает числовое значение , как правило, , правильное решение: также быть функцией, которая принимает один числовой аргумент и возвращает функцию с типом num -> num.

Понимание этого поможет вам понять тип подписей, но вы можете сделать это без. Здесь быстро и просто:

# let s x y z = x z (y z) ;;
val s : (’a -> ’b -> ’c) -> (’a -> ’b) -> ’a -> ’c = <fun>

Посмотрите на правую сторону. y дается один аргумент, поэтому он имеет тип a -> b, где a является типом z. x задается два аргумента, первый из которых z, поэтому тип первого аргумента также должен быть a. Тип (y z), второй аргумент - b, и, следовательно, тип x - (a -> b -> c). Это позволяет сразу вывести тип s.