Если у меня есть эта функция Haskell:Найти наименьшее неподвижная точка функции
Рассмотрим следующую функцию Haskell е:
f :: Int -> Int f 0 = 1 f x = x * x * f (x - 1)
Тогда как я могу вычислить его Fixpoint и наименее фиксированная точка (в закрытом виде)?
Ответ на этот вопрос:
Как это минимум Fixpoint рассчитывается? Я пытаюсь понять это, но все равно не повезло. Будет здорово, если кто-нибудь сможет мне это объяснить.
Легко видеть, что
f x = x * x * f (x-1)
= x * x * ((x-1) * (x-1) * f (x-2))
= x * x * ((x-1) * (x-1) * ((x-2) * (x-2) * f (x-3)))
= ...
= x * x * ((x-1) * (x-1) * ((x-2) * (x-2) * ... * 1)))
Теперь, чтобы ответить на ваш вопрос в комментариях о том, как это эквивалентно данной формуле (x!)^2 когда рекурсивный результат f (x-1) не квадратным, просто переставить факторы выше, с помощью ассоциативности и коммутативности (*) над Int:
x * x * ((x-1) * (x-1) * ((x-2) * (x-2) * ... * 1)))
= x * x * (x-1) * (x-1) * (x-2) * (x-2) * ... * 1
= (x * (x-1) * (x-2) * ... * 1) * (x * (x-1) * (x-2) * .. * 1)
= x! * x!
= (x!)^2
Как писал, это дно, так как функция является строгим. Но я предполагаю, что вам может понадобиться наименее фиксированная точка связанного с ним функционального '\ f n -> случая n из 0-> 1; x-> x * x * f (x-1) ', который имеет тип' (Int -> Int) -> (Int -> Int) 'и имеет нетривиальную наименее фиксированную точку. – chi
@chi, тогда какая будет наименее фиксированная точка ?, как я понимаю, как определить тип, но как написать LFP в закрытой форме. –
Разве это не 1? f 1 = 1 * 1 * f (0) = 1. На все остальные целые числа f x отличается от x, поэтому 1 является единственной фиксированной точкой. –