Лямбда-исчисление - четная функция в Haskell

#haskell #lambda-calculus

#haskell #лямбда-исчисление

Вопрос:

Итак, я изучаю лямбда-исчисление в Haskell, и я пытаюсь реализовать функцию isEven, которая возвращает true, если оно четное, и false в противном случае. Я знаю, что 0 четно, а затем 1 нечетно, и тогда каждое чередующееся число является альтернативой предыдущему, т. Е. Если единица нечетная, тогда 2 четно, тогда 3 нечетно. Могу ли я заставить функцию isEven проверить, равен ли входной сигнал 0, и если это не так, то как-то проверить, является ли его преемник четным или нечетным?

1. Это помогло бы увидеть точную конструкцию, с которой вы работаете. Это не моя инстинктивная реакция на то, как ее решить.

2. что вы подразумеваете под точной конструкцией?

3. Да, вы могли бы, хотя isEven 1176845632190017 это заняло бы довольно много времени.

4. На самом деле, я думаю, мне пришлось бы проверять предшественника, а не преемника, а затем возвращаться к нулю

5. @pythonhelpthrow Допустим, у вас был какой-то тип данных, подобный data Nat = Zero | Succ Nat . Тогда isEven :: Nat -> Bool это выглядело бы так isEven Zero = True; isEven (Succ n) = not (isEven n) . Но у вас есть какой-то другой тип данных или кодировка для Nat ; это то, чего не хватает в вашем вопросе.

Ответ №1:

Я предполагаю, что под «лямбда-исчислением» вы подразумеваете, что мы работаем с некоторыми цифрами, закодированными Церковью логическими значениями, а часть «Haskell» в основном не имеет отношения к вашему вопросу.

 isEven = n -> n flip True
flip = x y z -> x z y
True = x y -> x
False = x y -> y

Это работает немного иначе, чем то, как вы это выражаете.

Напомним, что цифра Черча n означает n повторяющиеся функциональные приложения. flip повторяется четное число раз id , таким образом n flip == id для четных n , n flip == flip для нечетных n . Также, flip True == False и flip False == True . Таким образом, конструкция правильно кодирует четность.