Операции над церковными списками в Хаскеле - PullRequest
Новая
       50

Операции над церковными списками в Хаскеле

4 голосов
/ 24 марта 2012

Я имею в виду этот вопрос 

type Churchlist t u = (t->u->u)->u->u

В лямбда-исчислении списки кодируются следующим образом: 

[] := λc. λn. n
[1,2,3] := λc. λn. c 1 (c 2 (c 3 n))

mapChurch :: (t->s) -> (Churchlist t u) -> (Churchlist s u)
mapChurch f l = \c n -> l (c.f) n

Я думаю о том, что другой списокфункции, которые я мог реализовать на церковных списках и успешно написал функцию conc2, которая объединяет 2 церковных списка 

conc2Church l1 l2 c n = l1 c (l2 c n)

Я также попробовал zipWithChurch, который работает как zipWith на обычных списках.Но я не могу найти решение.Кто-нибудь может мне помочь?

1 Ответ

4 голосов
/ 24 марта 2012

Вы хотите использовать настоящие кортежи или церковные кортежи? Я возьму первое.

Итак, начните с нужной подписи типа. Вы хотите, чтобы он брал 2 разных Churchlist с и генерировал Churchlist кортежей. 

churchZip :: Churchlist a u -> Churchlist b u -> Churchlist (a,b) u

Теперь, как бы вы это реализовали? Напомним, что Churchlist s представлены функцией, которая сворачивает их. Поэтому, если наш результат - Churchlist (a,b) u, мы хотим, чтобы он имел форму функции типа ((a,b) -> u -> u) -> u -> u (это, в конце концов, эквивалентно синониму типа Churchlist (a,b) u). 

churchZip l1 l2 c n = ???

Какой следующий шаг? Ну, это зависит. l1 пусто? А как насчет l2? Если один из них, то вы хотите, чтобы результат был пустым списком. В противном случае вы хотите создать пару первых элементов из каждого списка, а затем churchZip остальных. 

churchZip l1 l2 c n
  | isEmpty l1 || isEmpty l2 = n
  | otherwise                = c (churchHead l1, churchHead l2)
                                 (churchZip (churchTail l1) (churchTail l2) c n

Это поднимает некоторые вопросы.

  • Вам разрешено писать эту функцию рекурсивно? В чистом лямбда-исчислении вы должны писать рекурсивные функции с оператором фиксированной точки (он же комбинатор у).
  • Есть ли у вас churchHead, churchTail и isEmpty в наличии? Вы готовы их написать? Ты можешь их написать?
  • Есть ли лучший способ структурировать эту функцию? Все можно сделать с помощью сгиба (помните, l1 и l2 на самом деле являются функцией сгибания над собой), но является ли это чистым решением этой проблемы?

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

...