Hindley Milner Rodzaj Wnioskowanie w F #

Question

Może ktoś wyjaśnić krok po kroku typu wnioskowania w następujących F # programu:

let rec sumList lst = 
    match lst with 
    | [] -> 0 
    | hd :: tl -> hd + sumList tl 

I specjalnie chcą zobaczyć krok po kroku, w jaki sposób proces unifikacji w Hindley Milner działa.

Answer 1

Zabawne rzeczy!

Najpierw musimy wynaleźć typu rodzajowego do sumList: x -> y

i uzyskać prostych równań: t(lst) = x; t(match ...) = y

Teraz dodać równanie: t(lst) = [a] powodu (match lst with [] ...)

Wtedy równanie: b = t(0) = Int; y = b

Od 0 jest możliwy wynik meczu: c = t(match lst with ...) = b

Od drugiego wzoru: t(lst) = [d]; t(hd) = e; t(tl) = f; f = [e]; t(lst) = t(tl); t(lst) = [t(hd)]

Guess typu (typ ogólna) dla hd: g = t(hd); e = g

Następnie musimy typ dla sumList, więc musimy po prostu dostać bezsensowny typ funkcyjny teraz: h -> i = t(sumList)

Więc teraz wiemy: h = f; t(sumList tl) = i

Następnie z dodawania otrzymujemy: Addable g; Addable i; g = i; t(hd + sumList tl) = g

Teraz możemy przystąpić unifikacja:

t(lst) = t(tl)=>[a] = f = [e]=>a = e

t(lst) = x = [a] = f = [e]; h = t(tl) = x

t(hd) = g = i/\i = y=>y = t(hd)

x = t(lst) = [t(hd)]/\t(hd) = y=>x = [y]

y = b = Int/\x = [y]=>x = [Int]=>t(sumList) = [Int] -> Int

Pominąłem kilka trywialnych kroków, ale myślę, że możesz się dowiedzieć, jak to działa.