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

Question

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

Answer 1

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

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