¿Combinadores de puntos fijos para funciones a través de tipos personalizados?
-
15-09-2020 - |
Pregunta
La mayoría de los ejemplos del uso de combinadores de puntos fijos implican funciones que toman enteros a enteros (por ejemplo, factorial). En muchos casos, el punto fijo de una función sobre los números reales terminará siendo un número arbitrario racional o quizás irracional (un ejemplo famoso es el mapa logístico http://en.wikipedia.org/wiki/logistic_map ). En estos casos, el punto fijo puede no ser expresado en términos de tipos primitivos (tenga en cuenta que el Clojure tiene apoyo para los ratios). ¡Estoy interesado en descubrir sobre los combinadores de puntos fijos (y su implementación!) Que pueden calcular los puntos fijos de funciones a través de estos tipos "exóticos". En la medida en que las cosas como números irracionales tienen una representación decimal como secuencias infinitas, parece que este cálculo debe evaluarse perezosamente. ¿Alguna de estas evaluaciones perezosas (putativas) produce buenas aproximaciones a los puntos fijos verdaderos? Mis idiomas de destino son Python y Clojure, pero ciertamente no me importaría ver las implementaciones OCAML o haskell).
Solución
Encontrará tal función que calcule puntos fijos en blog de Andrej Bauer ;Por ejemplo, programas aparentemente imposibles y Infinite Búsqueda en tiempo finito .Eso es para el caso donde el punto fijo es en realidad en una 'distancia finita', para que se alcance.
Algunos de los puntos fijos de los que estás hablando no son de este tipo, ya que realmente están 'infinitamente lejos'.Estos son los tipos de puntos fijos que se utilizan en análisis computable .Básicamente, la teoría se trata de cómo obtener buenas aproximaciones al punto fijo.