Как реализовать эту функцию более высокого порядка

Question

Я новичок в функциональном программировании, и я пытаюсь выполнить следующее упражнение:

---

Учитывая тип

type Cont r a = (a -> r) -> r

Реализация следующего более высокого порядкаfunction

mapReader :: (a -> b) -> (Cont r a) -> Cont r b

---

Первым шагом будет упрощение типов, что дает:

mapReader :: (a -> b) -> ((a -> r) -> r) -> (b -> r) -> r

Далее определите параметры, которые должны быть предоставлены в этой функции.Эти параметры являются тремя функциями, поэтому мы получаем

mapReader :: (a -> b) -> ((a -> r) -> r) -> (b -> r) -> r
mapReader f g h = _1

Отсюда мы можем определить следующие типы:

f :: a -> b
g :: (a -> r) -> r
h :: b -> r
_1 :: r

Но теперь я застрял.Есть две функции, которые приводят к r, и одна из них содержит другую функцию (a -> r).Как я могу начать определять r?Любые советы приветствуются!

Answer 1

Таким образом, у вас есть

f ::  a -> b
h ::       b -> r
g :: (a ->      r) -> r

Также есть оператор прямой функциональной композиции

(>>>) :: (a -> b) -> (b -> r) -> (a -> r)

и оператор обратного приложения

(&) :: t -> (t -> r) -> r

, так что

f >>> h :: ......... -- what?

и

(f >>> h) & g :: ......... -- what else?

Можете ли вы придумать определения (>>>) и (&), только от их типов?

---

Позвольте мненачать с первого.

(>>>) ::   (a -> b)    -> (b -> r)     -> (a  -> r)

означает, что

(>>>) (f :: a -> b)    :: (b -> r)     -> (a  -> r)
(>>>) (f :: a -> b) (g ::  b -> r)     :: (a  -> r)
(>>>) (f :: a -> b) (g ::  b -> r)  (x ::  a) :: r

Итак, мы снова записываем их

f :: a -> b
g ::      b -> r
x :: a
f x ::    b
g (f x) ::    ....

И это все.

Самое важное правило, котороемы использовали здесь, это

x   :: a
f   :: a -> r
f x ::      r

Answer 2

У нас есть

f :: a -> b
g :: (a -> r) -> r
h :: b -> r

и нам нужно

_1 :: r

Есть два способа сделать r: g и h.

Давайте попробуем использовать h.h принимает аргумент типа b.Единственный способ получить один из них - использовать f.f принимает аргумент типа a, и ... у нас нет никакого способа получить один из них.

Так что теперь давайте попробуем использовать g вместо:

mapReader f g h = g _2

Нам говорят

_2 :: a -> r

Поскольку мы создаем функцию, мы можем применять лямбда-абстракцию как обычно:

mapReader f g h = g (\a -> _3)

a :: a
_3 :: r

Но подождите ... теперь мы имеют и a, поэтому мы можем вернуться к нашей первой попытке:

mapReader f g h = g (\a -> h (f a))

или, более компактно,

mapReader f g h = g (h . f)

---

Что если вместо этогочтобы вернуться к первой попытке, мы сделали это вторым путем снова ?

mapReader' f g h =
  g (\a1 -> g (\a2 -> _4))

_4 :: r

Вы можете идти этим путем вечно, но вы также можете остановиться здесь двумя различными способами:

mapReader2 f g h =
  g (\_ -> g (h . f))

mapReader3 f g h =
  g (\a1 -> g (\_ -> h (f a1)))

Ой!Это три разные функции, которые имеют одинаковый тип, и, как показано, этот подход можно использовать для генерации бесконечного семейства функций!Как вы можете решить, какой вы хотите?Вы должны рассмотреть намерение.Аргумент g является продолжением, поэтому вы хотите составить функцию с тем, что вы передаете g, а не вызывать g несколько раз.Таким образом, mapReader является «правильным» ответом.

Точнее, mapReader должен отображать морфизмы для продолжения функтор .Это требует, в частности, что

mapReader id = id

То есть

mapReader id g h = g (h . id)
  = g h

Это безусловно верно для правильного определения, но не для любого другого.

Answer 3

Начните с того, что вы можете сделать с тремя аргументами.

1. Вы можете составить f и h: h . f :: a -> r.
2. Вы можете применить g к h . f: g (h . f) :: r.

Так что вы можете просто сказать, что mapReader f g h = g (h . f).Здесь недостаточно информации, чтобы указать, что такое r;полностью зависит от того, какие аргументы g и h даны mapReader.