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

[deniok]

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

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

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

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

Comments

[sassa-nf.livejournal.com]

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

[deni-ok.livejournal.com]

Да, это кратчайшее из известных мне, даже если переписать в чистой лямбде, без (.)

Prelude> :t \f g -> g (\y -> g ((\x -> f) y))
\f g -> g (\y -> g ((\x -> f) y))
  :: (t1 -> t) -> ((t1 -> t) -> t) -> t

[migmit.livejournal.com]

Эм...

Prelude> :t \f g -> g (\a -> g f)
\f g -> g (\a -> g f) :: (t -> t1) -> ((t -> t1) -> t1) -> t1

Первая попытка решить вторую задачу.

[slobin.livejournal.com]

Ух ты!

... Мимореальный музей ...

[deni-ok.livejournal.com]

Ты - лучший!