Найдите функции Хаскелла f, g такие, что f g = f . г

Question

Изучая Haskell, я столкнулся с проблемой найти две функции f а также gтакой, что f g а также f . g эквивалентны (и всего, поэтому такие вещи, как f = undefined или же f = (.) f не в счет). Данное решение таково, что f а также g оба равны \x -> x . x (или же join (.)).

(Я отмечаю, что это не специфично для Хаскеля; это можно выразить в чистой комбинаторной логике как "найти f а также g такой, что f g = B f g", и данное решение будет затем переводить в f = g = W B.)

Я понимаю, почему данное решение работает, когда я расширяю его, но я не понимаю, как вы могли бы его найти, если бы вы его еще не знали. Вот как далеко я могу получить:

• f g = f . g (дано)
• f g z = (f . g) z (Эта-расширение обеих сторон)
• f g z = f (g z) (упростить RHS)

И я не знаю, как действовать дальше. Что я буду делать дальше, пытаясь найти решение?

Answer 1

Я обнаружил, что можно найти семейство решений, рассмотрев вычисление церковных чисел. В церковном кодировании умножение выполняется путем составления церковных чисел, а возведение в степень - путем применения базы к показателю степени. Таким образом, если f Церковная кодировка некоторого числа x, а также g Церковная кодировка некоторого числа y, затем f g = f . g подразумевает y^x = x*y, Любые неотрицательные целочисленные решения этого уравнения переводятся в решения исходной задачи. Примеры:

• x=1, y=0, f=id, g=const id
• x=1, y=1, f=id, g=id
• x=1, y=2, f=id, g=join (.)
• поскольку y^1 = y = 1*y для всех yимеет смысл, что f=id работает для всех церковных цифр g, Это действительно так, и на самом деле, как отметил Рейн Хенрикс, это верно для всех gи это легко проверить осмотром.
• x=2, y=0, f=join (.), g=const id
• x=2, y=2, f=join (.), g=join (.)
• x=3, y=0, f=(.) <*> join (.), g=const id
• поскольку 0^x = 0 = x*0 за все позитивное xимеет смысл, что g=const id работает для всех положительных церковных цифр f, (Это не работает для f=const idЦерковная цифра 0, которая имеет смысл, так как 0^0 это неопределенная форма.)