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

[deniok]

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

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

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

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

Comments

Re: Наиболее общий тип

[dmytro starosud (from livejournal.com)]

То есть, решение для второго - это решение для третьего?
*(у меня плохой функциональный бекграунд, поэтому отошлите куда-то, если так будет лучше - литература имеется ввиду)

Re: Наиболее общий тип

[nponeccop.livejournal.com]

Решение для третьего является решением для второго и первого, решение для второго является решением для первого. Но не наоборот!

Re: Наиболее общий тип

[dmytro starosud (from livejournal.com)]

Скажите, пожалуйста, ниже решения для второго и третьего?
\f g -> g (\x -> g f)
\f g -> g (\y -> g ((\x -> f) y))

Re: Наиболее общий тип

[nponeccop.livejournal.com]

Любой из этих двух термов является решением всех трех задач.

Re: Наиболее общий тип

[dmytro starosud (from livejournal.com)]

Спасибо большое!
Простите, я уже наверное достал.
Скажите, пожалуйста, есть ли терм, который будет решением второго задания но не третьего? И какой?

Re: Наиболее общий тип

[deni-ok.livejournal.com]

\f g -> g (\x -> f x)

Re: Наиболее общий тип

[dmytro starosud (from livejournal.com)]

Спасибо большое!