Большинство примеров использования комбинаторов с фиксированной точкой включают функции, которые принимают целые числа в целые числа (например, факториал). Во многих случаях неподвижная точка функции над действительными числами окажется произвольным рациональным или, возможно, иррациональным числом (известным примером является логистическая карта http://en.wikipedia.org/wiki/Logistic_map). В этих случаях фиксированная точка не может быть выражена в терминах примитивных типов (обратите внимание, что у Clojure есть поддержка отношений). Мне интересно узнать о комбинаторах с фиксированной точкой (и их реализации!), Которые могут вычислять фиксированные точки функций над этими «экзотическими» типами. Поскольку такие вещи, как иррациональные числа, имеют десятичное представление как бесконечные последовательности, кажется, что это вычисление должно оцениваться лениво. Любая из этих (предполагаемых) ленивых оценок дает хорошие аппроксимации истинным фиксированным точкам? Мои целевые языки - Python и Clojure, но я, конечно, не против видеть какие-либо реализации OCaml или Haskell).Комбинаторы с фиксированной точкой для функций по специальным типам?
4
A
ответ
2
Вы найдете такую функцию, которая вычисляет фиксированные точки на блоге Andrej Bauer; например seemingly impossible programs и infinite search in finite time. Это для случая, когда фиксированная точка на самом деле находится на «конечном расстоянии», так что она будет достигнута.
Некоторые из фиксированных точек, о которых вы говорите, не такие, как они действительно «бесконечно далеко». Это типы неподвижных точек, которые используются в Computable Analysis. В принципе, существует теория о том, как получить хорошие приближения к неподвижной точке.