Как я могу сделать комбинатор с такой подписью типа?

Question

Я пытался сделать комбинатор с такой подписью типа:

(a -> b -> c) -> (c -> d -> e) -> a -> b -> d -> e

Я прошел через Data.Aviary.Birds и все сайты помощи по молчаливому программированию, которые я могу найти, но безрезультатно. Кроме того, если есть общий алгоритм для их создания, это было бы очень полезно, но не обязательно.

Answer 1

Наше определение начнется так:

foo :: (a -> b -> c) -> (c -> d -> e) -> a -> b -> d -> e
foo abc cde a b d = e

Теперь давайте заполним пропущенные биты.

Нам нужен e; единственный способ получить это, применяя вторую функцию к c а также d,

e = cde c d

Нам уже дали d, но нам нужен c, Как мы получаем c? Применяя первую функцию к a и b,

c = abc a b

Нам даны оба из них, поэтому мы сделали.

foo :: (a -> b -> c) -> (c -> d -> e) -> a -> b -> d -> e
foo abc cde a b d = e
  where
    e = cde c d
    c = abc a b

Мы могли бы остановиться здесь. Это совершенно хорошее определение.

---

Но если мы хотим попытаться сделать это более кратким, давайте начнем с замены определения e

foo abc cde a b d = cde c d
  where
    c = abc a b

а затем из c

foo abc cde a b d = cde (abc a b) d

Мы сразу видим, что мы можем это уменьшить, чтобы удалить d,

foo abc cde a b = cde (abc a b)

Тип теперь немного более общий. d -> e свернулся в одну переменную типа, так как это может быть что угодно.

foo :: (a -> b -> c) -> (c -> de) -> a -> b -> de

Теперь мы можем видеть в вольере, что наш комбинатор на самом деле - черный дрозд, перевернутый.

blackbird :: (c -> d) -> (a -> b -> c) -> a -> b -> d

foo :: (a -> b -> c) -> (c -> de) -> a -> b -> de
foo = flip blackbird

И действительно, если мы посмотрим на источник для черного дрозда, это будет очень похоже на то, что мы написали.

-- | B1 combinator - blackbird - specs 'oo'.
blackbird :: (c -> d) -> (a -> b -> c) -> a -> b -> d
blackbird f g x y = f (g x y)

---

Можем ли мы пойти больше без очков? Мы могли бы рассмотреть не спеша abc

foo abc cde a b = cde (uncurry abc (a, b))

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

foo abc cde a b = (cde . uncurry abc) (a, b)

и снова карри

foo abc cde a b = curry (cde . uncurry abc) a b

И теперь мы можем отрубить еще два параметра.

foo abc cde = curry (cde . uncurry abc)

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

foo = flip $ \cde abc -> curry (cde . uncurry abc)

переписать правую половину, чтобы сделать ее бессмысленной

foo = flip $ \cde abc -> (curry . ((cde .) . uncurry)) abc

и это уменьшить еще раз

foo = flip $ \cde -> curry . ((cde .) . uncurry)

и сделать последний нелепый шаг

foo = flip $ (curry .) . (. uncurry) . (.)

Мы теперь без очков!

Answer 2

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

f :: (a -> b -> c) -> (c -> d -> e) -> a -> b -> d -> e

и это возвращается с

f a b c d = b (a c d)

Ницца. Теперь зайдите на http://pointfree.io/. Вставьте в определение от Джинн, и это говорит

f = flip ((.) . (.))

Готово.