Создание списка упорядоченных пар в лямбда-исчислении с использованием рекурсии - PullRequest
Новая
       31

Создание списка упорядоченных пар в лямбда-исчислении с использованием рекурсии

0 голосов
/ 28 апреля 2018

Мои данные представляют собой два списка: l = [x1, x2, x3, ..., xn] и k = [y1, y2, y3, ..., yn]

Я хочу вывод y = [(x1, y1), (x2, y2), (x3, y3) ... (xn, yn)].

Как я могу применить рекурсию к своему коду? Я мог бы сделать это для первого пункта с f = \l k. (cons (pair (head l) (head k)) empty) но я не совсем понимаю, как использовать рекурсию для создания других элементов.

Функция «head» возвращает первый элемент списка, а функция «tail» возвращает список без первого элемента.

1 Ответ

0 голосов
/ 25 сентября 2018

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

cons    -- construct a list from a node and another list
empty   -- the empty list
head    -- retrieve the first node value of a list
tail    -- retrieve all but the first node of a list
pair    -- pair values into a tuple
isEmpty -- return `true` if a list is `empty`, `false` otherwise
true    -- return the first argument
false   -- return the second argument

Тогда мы можем рекурсивно сжать списки следующим образом: 

ZIP = λlk. isEmpty l -- "if the list is empty…"
           empty     -- "return an empty result. Else…"
           (cons     -- "return a new list, containing…"
               (pair (head l) (head k))  -- "the zipped heads, and…"
               (ZIP  (tail l) (tail k))) -- "everything else zipped."

Проблема, конечно, заключается в том, что исходное лямбда-исчисление не имеет рекурсии . Вы не можете ссылаться на имя функции в ее собственном определении. Ответ заключается в использовании комбинатора с фиксированной точкой, например, знаменитый Y комбинатор . 

ZIP = Y (λzlk. isEmpty l empty (cons (pair (head l) (head k)) (z (tail l) (tail k)))

Определение Y: 

Y = λf.(λx.f(x x))(λx.f(x x))

Распутывание того, как именно это работает - впечатляющая часть умственной гимнастики, которая не совсем подходит для этого вопроса, но с использованием довольно проста. В общем, если у вас есть желаемое (но недопустимое, в необработанном LC) рекурсивное определение, подобное этому: 

R = λ ??? . ??? R ???

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

R = Y (λr ??? . ??? r ???)

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

...