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

Question

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

Это искусственный пример, который я составил: так что можно определить рекурсивную факториальную функцию в 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 вместо использования факториала имени?

Answer 1

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

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

По сути, у него нет имени, поскольку это лямбда-выражение, поэтому вы берете функцию в качестве аргумента. Фикс применяет функцию к себе «бесконечно» много раз:

fix f = f (fix f)

и определено в Data.Function.

Answer 2

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

fixpoint f x = f (fixpoint f) x

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

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

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

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

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

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

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

Answer 3

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

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

Answer 4

Оуэн активен с помощью функции исправления

Prelude> fix f = f (fix f)
Prelude> fix (\f n -> if n == 0 then 1 else n * f (n - 1)) 6
720

Безымянная лямбда-функция завершается автоматически, даже если исправления нет.Функция исправления Оуэна превосходит функцию исправления, обычно используемую в Haskell:

fix :: (a -> a) -> a
fix f = let {x = f x} in x

Обе функции разрешают анонимные рекурсивные лямбда-функции