Фиксированные точечные комбинаторы для функций над пользовательскими типами?

Question

Большинство примеров использования комбинаторов фиксированных точек включают функции, которые предпринимают целые числа целых чисел (например, факториал). Во многих случаях фиксированная точка функции над реальными числами завершится произвольным рациональным или, возможно, иррациональным числом (известный пример - это логистическая карта http://en.wikipedia.org/wiki/logistic_map ). В этих случаях фиксированная точка не может быть выражена в терминах примитивных типов (примечание, хотя Clojure имеет поддержку соотношения). Я заинтересован в том, чтобы узнать о комбинаторах фиксированных точек (и их реализацию!), Которые могут вычислить фиксированные точки функций над этими «экзотическими» типами. Поскольку вещи, такие как иррациональные числа, имеют десятичное представление как бесконечные последовательности, кажется, что это вычисление должно быть оценено лениво. Есть ли какие-либо из этих (предполагаемых) ленивых оценок, дают хорошие приближения к истинным фиксированным точкам? Мои целевые языки являются Python и Clojure, но я, конечно, не против видеть какие-либо реализации Ocaml или Haskell).

Answer 1

Вы найдете такую функцию, которая вычисляет фиксированные точки на блог Andrej Bauer ;Например, Казалось бы, невозможные программы и Бесконечный поиск в конечном времени/ a>.Это для случая, когда фиксированная точка на самом деле находится на «конечном расстоянии», так что оно будет достигнуто.

Некоторые из фиксированных точек, о которых вы говорите, не имеют такого рода, как они действительно «бесконечно далеко».Это типы фиксированных точек, которые используются в Вычислимый анализ .В основном теория есть все о том, как получить хорошие приближения к фиксированной точке.