deniok: (Default)
deniok ([personal profile] deniok) wrote2012-06-28 05:04 pm

Термы с заданными типами

Три задачки с экзамена, в порядке усложнения условия.

Написать замкнутый терм типа (a -> b) -> ((a -> b) -> b) -> b.

Написать замкнутый терм типа (a -> b) -> ((a -> b) -> b) -> b, которому нельзя приписать тип c -> (c -> b) -> b.

Написать замкнутый терм с наиболее общим типом (a -> b) -> ((a -> b) -> b) -> b.

[identity profile] deni-ok.livejournal.com 2012-06-28 03:05 pm (UTC)(link)
Да, так, только последнее желательно без всяких внешних конструкций типа head и []. В чистой лямбде.

[identity profile] slobin.livejournal.com 2012-06-28 03:09 pm (UTC)(link)
Я сам понимаю, что желательно. Но пока торможу. :-(

... Какой я математик? Я флюктуация. ...

[identity profile] slobin.livejournal.com 2012-06-28 03:32 pm (UTC)(link)
\f g -> (\i -> i $ g (\x -> i $ f x))(\x -> x)

Наверное, это можно как-то покороче записать, но в таком виде оно мне в голову пришло.

... Старый, нищий, уродливый и бездарный оптимист ...

[identity profile] deni-ok.livejournal.com 2012-06-28 04:28 pm (UTC)(link)
Да, там ниже [livejournal.com profile] sassa_nf привёл более компактное решение.