Как определяется тип этой функции?

Question

Я почесал голову, чтобы выяснить подпись этой функции

let make_rec f_norec = 
    let rec f x = f_norec f x in 
    f 

, который должен быть

val make_rec : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>.

Обратите внимание, что существует странное рекурсивное определение. Определенно, мне не хватает знаний. Может ли кто-нибудь показать мне, как вычислить тип функции (как это делает система вывода типов)?

Большое спасибо.

Answer 1

Начиная с внутренними из них, и работа наружу:

1. будем называть тип xa
2. затем f имеет тип a -> b где b является тип результата f
3. f_norec принимает f и x, и он должен возвращать тот же тип, что и f, следовательно (a->b) -> a -> b
4. make_rec принимает f_norec, и он возвращает f. Следовательно, ((a->b)->a->b) -> (a->b). По синтаксическим причинам последнюю пару круглых скобок можно опустить.