podpisy/typy w programowaniu funkcjonalnym (OCaml)

Question

Zacząłem uczyć się programowania funkcjonalnego (OCaml), ale nie rozumiem jednego ważnego tematu dotyczącego fp: sygnatur (nie jestem pewien, czy to nazwa własna). Kiedy wpisuję coś i skompilować z SML, mam na przykład:

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

to trywialne, ale nie wiem, dlaczego to:

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

daje wynik:

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

Przypuszczam, że ten temat jest dla wielu z was podstawowym zadaniem, ale proszę o pomoc, ponieważ nie znalazłem w Internecie żadnego oznaki OCaml (jest kilka artykułów na temat podpisów w Haskell, ale nie wyjaśnienia).

Jeśli ten wątek jakoś przetrwa, zamieścić tu kilka funkcji, które sprawiło, że podpisy mylić:

# let nie f a b = f b a ;; (* flip *) 
val nie : (’a -> ’b -> ’c) -> ’b -> ’a -> ’c = <fun> 

# let i f g a b = f (g a b) b ;; 
val i : (’a -> ’b -> ’c) -> (’d -> ’b -> ’a) -> ’d -> ’b -> ’c = <fun> 


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

# let callCC f k = f (fun c d -> k c) k ;; 
val callCC : ((’a -> ’b -> ’c) -> (’a -> ’c) -> ’d) -> (’a -> ’c) -> ’d = <fun> 

Dziękujemy za pomoc i wyjaśnienia.

Answer 1

Istnieje kilka pojęć potrzebnych do zrozumienia sensu tego typu podpisu i nie wiem, które z nich już zrobić, więc Starałem się wyjaśnić każdą ważną koncepcję:

currying

Jak wiesz, jeśli masz typ foo -> bar, opisuje to funkcję pobierającą argument typu foo i zwracającą wynik typu bar. Ponieważ -> jest stowarzyszeniem prawym, typ foo -> bar -> baz jest taki sam jak foo -> (bar -> baz) i dlatego opisuje funkcję pobierającą argument typu foo i zwracającą wartość typu bar -> baz, co oznacza, że ​​zwracana wartość jest funkcją przyjmującą wartość typu bar i zwracającą wartość wartość typu baz.

Taka funkcja może być wywołana jak my_function my_foo my_bar, które z powodu aplikacja funkcja lewej zrzeszania się, jest taki sam jak (my_function my_foo) my_bar, to znaczy dotyczy my_function do argumentu my_foo a następnie stosuje się funkcję, która jest zwracana jako wynik do argumentu my_bar.

Ponieważ można to tak nazwać, funkcja typu foo -> bar -> baz jest często nazywana "funkcją przyjmującą dwa argumenty", a ja to zrobię w pozostałej części tej odpowiedzi.

zmiennych typu

Jeśli zdefiniować funkcję jak let f x = x, będzie miał typ 'a -> 'a. Ale 'a nie jest tak naprawdę typem zdefiniowanym gdziekolwiek w standardowej bibliotece OCaml, więc co to jest?

Dowolny typ rozpoczynający się od ' to tak zwana zmienna . Zmienna typu może oznaczać dowolny możliwy typ. Tak więc w powyższym przykładzie f można wywołać z int lub string lub list lub cokolwiek w ogóle - to nie ma znaczenia.

Co więcej, jeśli zmienna tego samego typu pojawi się w podpisie typu więcej niż jeden raz, będzie oznaczać ten sam typ. Tak więc w powyższym przykładzie oznacza to, że typ zwracany f jest taki sam jak typ argumentu. Więc jeśli f jest wywoływana z int, zwraca wartość int. Jeśli jest wywoływana z string, zwraca wartość string i tak dalej.

Tak więc funkcja typu 'a -> 'b -> 'a może przyjmować dwa argumenty dowolnego typu (które mogą nie być tego samego typu dla pierwszego i drugiego argumentu) i zwraca wartość tego samego typu co pierwszy argument, podczas gdy funkcja typu 'a -> 'a -> 'a wymaga dwóch argumentów tego samego typu.

Jedna uwaga na temat wnioskowania o typie: O ile wyraźnie nie podasz funkcji podpisu typu, OCaml zawsze wnioskuje o najbardziej ogólnym możliwym typie. Więc jeśli funkcja nie używa żadnych operacji, które działają tylko z danym typem (na przykład +), wnioskowany typ będzie zawierał zmienne typu.

Teraz wyjaśnić typ ...

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

Podpis ten typ mówi, że something jest funkcją biorąc cztery argumenty.

Typ pierwszego argumentu to 'a -> 'b -> 'c. To znaczy. funkcja przyjmująca dwa argumenty o arbitralnym i ewentualnie różnych typach i zwracająca wartość dowolnego typu.

Typ drugiego argumentu to 'a -> 'd -> 'b. Jest to znowu funkcja z dwoma argumentami. Ważne jest, aby zauważyć, że pierwszy argument funkcji musi mieć ten sam typ, co pierwszy argument pierwszej funkcji, a zwracana wartość funkcji musi mieć ten sam typ co drugi argument pierwszej funkcji.

Typ trzeciego argumentu to 'a, który jest także typem pierwszych argumentów obu funkcji.

Wreszcie typ czwartego argumentu to 'd, który jest typem drugiego argumentu drugiej funkcji.

Wartość zwracana będzie typu 'c, tj. Typem powrotu pierwszej funkcji.

Answer 2

Jeśli naprawdę interesujesz się tym tematem (i masz dostęp do biblioteki uniwersyteckiej), przeczytaj Wadler's doskonałe (jeśli nieco przestarzałe) "Wprowadzenie do programowania funkcjonalnego". Wyjaśnia podpisy typów i typy wnioskowania w bardzo ładny i czytelny sposób.

Dwie dalsze wskazówki: Zwróć uwagę, że strzałka -> jest prawostronna, więc możesz wstawiać elementy z prawej strony, co czasami pomaga zrozumieć rzeczy, np. a -> b -> c jest tym samym, co a -> (b -> c). Jest to połączone z drugą podpowiedzią: funkcje wyższego rzędu. Można robić takie rzeczy jak

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

tak w FP, myśląc o „dodać” jako funkcja, która musi wziąć dwa parametry liczbowe i zwraca wartość liczbowa jest nie ogólnie słuszne zrobić: to może być także funkcją, która pobiera jeden argument liczbowy i zwraca funkcję o numerze num -> num.

Zrozumienie tego pomoże ci zrozumieć podpisy typów, ale możesz to zrobić bez. Tutaj, szybko i łatwo:

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

Zobacz po prawej stronie. y ma jeden argument, więc jest typu a -> b, gdzie a jest typem z. x otrzymuje dwa argumenty, z których pierwszym jest z, więc typ pierwszego argumentu musi być również a. Typ (y z), drugi argument, to b, a zatem typ x to (a -> b -> c). Umożliwia to natychmiastowe odjęcie typu s.