Vaje: izpeljava tipov

Za vsakega od naslednjih izrazov izpeljite njegov glavni tip, ali ugotovite, da ga nima. Nato preverite odgovor še v OCamlu.

Naloga

Izpeljite glavni tip izraza

fun x -> fun y -> x, y, y

Naloga

Izpeljite glavni tip izraza

fun f -> fun g -> f (g 42)

Naloga

Izpeljite glavni tip izraza

if 3 < 5 then fun x -> x else fun y -> y, y

Naloga

Izpeljite glavni tip rekurzivne funkcije

let rec f x = if x = 0 then 1 else x * f (x - 1)

Naloga

Izpeljite glavni tip funkcije map:

let rec map f l = 
    match l with
    | [] -> []
    | x :: xs -> f x :: map f xs

Navodilo: uporabite pravilo za rekurzivne funkcije, ter pravila za sezname in match:

• prazen seznam [] ima tip α list, kjer je α nov parameter

• sestavljen seznam e₁ :: e₂:

  • izpeljemo tip τ₁ izraza e₁ in dobimo enačbe E₁
  • izpeljemo tip τ₂ izraza e₂ in dobimo enačbe E₂

  Tip e₁ :: e₂ je τ₁ list, z enačbami E₁, E₂ in τ₂ = τ₁ list.

• izraz match e₁ with [] -> e₂ | x :: xs -> e₃:

  • izpeljemo tip τ₁ izraza e₁ in dobimo enačbe E₁
  • izpeljemo tip τ₂ izraza e₂ in dobimo enačbe E₂
  • uvedemo nov parameter α, zabeležimo x : α in xs : α list, izpeljemo tip τ₃ izraza e₃ in dobimo enačbe E₃

  Tip match e₁ with [] -> e₂ | x :: xs -> e₃ je τ₂ z enačbami E₁, E₂, E₃, τ₁ = α list in τ₂ = τ₃.