Как написать рекурсивное выражение лямбды в Haskell?

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

Это искусственный пример, который я составил: Таким образом, можно рекурсивно определить факториальную функцию в Haskell следующим образом

factorial :: Integer -> Integer 
factorial 1 = 1
factorial (n + 1) = (n + 1) * factorial n

Теперь мне нужна функция f такая, что f n = (factorial n) + 1. Вместо того, чтобы использовать имя для factorial n (т.е. Определяя его перед рукой), я хочу определить f, где factorial n задано лямбда-выражение в определении f. Могу ли я использовать рекурсивное определение лямбда в f вместо использования имени factorial?

Ответы

Ответ 1

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

fixpoint f x = f (fixpoint f) x

Если предположить, что такой комбинатор существует, мы можем записать рекурсивную функцию как

factorial = fixpoint (\ff n -> if n == 1 then 1 else n * ff(n-1))

Единственная проблема заключается в том, что fixpoint сам по-прежнему рекурсивный. В чистом исчислении лямбда существуют способы создания комбинаторов фиксированных точек, которые состоят только из лямбда, например классического "Y combinator":

fixpoint f = (\x -> f (x x)) (\x -> f (x x))

Но у нас все еще есть проблемы, потому что это определение не хорошо типизировано в соответствии с Haskell - и можно доказать, что нет способа написать хорошо подобранный комбинатор исправлений, используя только приложения лямбда и функции. Это можно сделать, используя вспомогательный тип данных для shoehorn в рекурсии определенного типа:

data Paradox a = Self (Paradox a -> a)
fixpoint f = let half (Self twin) = f (twin (Self twin))
             in half (Self half)

(Обратите внимание, что если удаляются инъекции и проекции из однотипного типа данных, это как раз Y combinator!)

Ответ 2

Да, используя функцию фиксированной точки fix:

fact :: Int -> Int
fact = fix (\f n -> if n == 0 then 1 else n * (f (n-1)))

В принципе, у него нет имени, так как это выражение лямбда, поэтому вы принимаете функцию в качестве аргумента. Fix применяет функцию к себе "бесконечно" много раз:

fix f = f (fix f)

и определяется в Data.Function.

Ответ 3

Почему мы используем лямбда вместо let in?

Prelude> (let fib n = if n == 1 then 1 else n * fib(n-1) in fib ) 4
24