Functional Programming 2025/26 fall

Kodutöö 4

1. {$\lambda$}-termid

Kas tegemist on {$\lambda$}-termiga? Kui jah, kirjuta ümber ühe parameetriga lambdadega ja pane kõik sulud

1. {$ \lambda{} a\ (b.\ b\ a) \lambda{} z. z$}
2. {$ f \lambda{} x\ y.\ g\ x\ y\ z$}
3. {$ f \lambda{} z.\ z\ \lambda{} x\ y.\ g\ x\ y$}
4. {$ \lambda{}\lambda{}2\ 1$}
5. {$ \lambda{} a\ b.\ b\ a\ \lambda{} z.\ z$}

2. Muutujate klassifitseerimine

Märgi iga muutuja kohta, kas see on vaba või millise parameetriga see seotud on.

1. {$ \lambda{}f.\ (\lambda{}g.\ g\ x)\ (\lambda{}x.\ f\ x)$}
2. {$ (\lambda{}x.\ (\lambda{}g.\ g\ x))\ x$}
3. {$ \lambda{}g.\ (\lambda{}f.\ f\ x)\ (\lambda{}x.\ g\ x)$}
4. {$ z\ (\lambda{}h\ x.\ (\lambda{}f.\ h\ f)\ x)$}
5. {$ \lambda{}h\ x.\ \text{cond}\ h\ (\text{add}\ 1\ x)\ k$}

3. Substitutsioon

Leia substitutsiooni tulemus!

1. (λf. f y(λx.x))[y→λx y. f x]
2. (λx. f (x x))(λx. f (x x))[f→λx y. y]
3. (λx g y.x g y)[g→x g y]
4. ((λx y. y) y)[y→λx. y]

4. Reduktsioon

Redutseeri väärtuseks (s.t. nii palju kui saab) a) normaaljärjekorras ja b) aplikatiivjärjekorras.

1. (λx. add x) (add 1 2) (mul 2 2)
2. (λf. f f) ((λx. b) (λx. x))
3. (λf. (λg. f) f) ((λx. b) (λx. x))
4. ((λy. (λx. y)) 1 ((λx. x x) (λx. x x)))
5. ((λx. x)(λx. (λy. x w) r) (λx. y))
6. (λx. cond (iszero x) (add x) (mul x)) 1 (add 1 2)