Пусть имеются взаимно-рекурсивное определение термов foo и bar. В общем виде его можно записать так:
foo = P foo bar
bar = Q foo bar
Здесь P и Q — некоторые термы, не содержащие ни foo, ни bar. Используя Y-комбинатор, найдите нерекурсивные определения для foo и bar.
Постарайтесь найти максимально «компактное» решение, с наименьшим количеством Y-комбинаторов
Для решения задачи, давайте сначала разберемся с взаимно-рекурсивными определениями термов foo и bar. Мы имеем:
Где P и Q — это термы, которые не содержат foo и bar. Мы можем использовать Y-комбинатор для создания рекурсивных функций.
Y-комбинатор позволяет нам определять рекурсивные функции в лямбда-исчислении. Он выглядит следующим образом:
Y = λf.(λx.f (x x)) (λx.f (x x))
Теперь, чтобы избавиться от рекурсии, мы можем воспользоваться Y-комбинатором для создания функций, ...
Не нашел нужную задачу?