Как читать подписи типа F#?

Question

Я борюсь с обозначением подписи типа F#. Например, допустим, у вас есть функция Fold:

let rec Fold combine acc l =
...

который может иметь подпись этого типа:

('a -> 'b -> 'a) -> 'a -> list<'b> -> 'a

который я бы прочитал как

функция, которая имеет три аргумента:

• функция, которая принимает 'a, a' b и возвращает a '
• и
• список 'б

и возвращает 'a.

Но тогда для моего мозга пещерных людей было бы больше смысла выразить это как

('a, 'b -> 'a), 'a, list<'b> -> 'a

Я уверен, что есть семантическая причина, почему параметры разделяются стрелкой точно так же, как и тип возвращаемого значения функции, но почему-то я упускаю это и до сих пор не нашел четкого объяснения в книгах / статьях. Каждый раз, когда я вижу сигнатуру типа, мне приходится останавливаться, чтобы понять это. Я чувствую, что просто скучаю по той маленькой части головоломки, которая делает "расшифровку" очевидной.

Может кто-нибудь, пожалуйста, просветите меня?

Answer 1

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

Вы читаете о первой функции правильно. Для мгновенного дешифрования подписи типа выражаются так:

val functionName = inputType1 -> inputType2 -> ... -> inputTypeN -> returnType

Обычно обозначение стрелки указывает на то, что функция может быть карри.

// val add4 : int -> int -> int -> int -> int
let add4 a b c d = a + b + c + d;;

// val f : (int -> int)
let f = add4 1 2 3 // returns (int -> int) waiting for last argument

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

// val add4 : int -> int -> int -> int -> int
let add4 = (fun a -> (fun b -> (fun c -> (fun d -> a + b + c + d))));;

// val f : (int -> int)
let f = fun x -> add4 1 2 3 x

Если вы думаете об этом, то add4 подпись эквивалентна этому:

val add4 : int -> (int -> (int -> (int -> int) ) )

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

Answer 2

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

('a -> 'b -> 'a) -> ('a -> (list<'b> -> 'a))

Answer 3

Вы можете написать аналогичную функцию в F#, которая имеет тип, который вы предлагаете (но в F# это будет написано как ('a * 'b -> 'a) * 'a * list<'b> -> 'a, Однако преимущество существующей функции заключается в том, что ее можно частично применить, просто указав префикс аргументов. Например:

let sum = List.fold (+) 0

Используя ваше определение, вы должны написать

let sum l = List.fold((fun (x,y) -> x + y), 0, l)

Answer 4

Причина в том, что в функциональном программировании каждая функция имеет только один параметр.

Допустим, у вас есть функция Sum, которая называется:

int -> int -> int

Требуется 2 int и вернуть один int. Теперь, если вы вызовете эту функцию, просто передав одну int, вы не получите никакой ошибки компилятора, скорее, возвращаемое значение будет иметь тип int -> int. Итак, вы видите, что обозначение стрелки соответствует этому поведению. Такое поведение известно как карри. Проверьте: http://en.wikipedia.org/wiki/Currying