Combinatori a punti fissi per funzioni su tipi personalizzati?

Question

La maggior parte degli esempi dell'uso dei combinatori di punti fissi coinvolge le funzioni che portano interi su interi (ad esempio fattoriale). In molti casi il punto fisso di una funzione rispetto ai numeri reali finirà per essere un numero razionale arbitrario o forse irrazionale (un esempio famoso è la mappa logistica http://en.wikipedia.org/wiki/logistic_map ). In questi casi il punto fisso non può essere espresso in termini di tipi primitivi (nota però che il clojure abbia supporto per i rapporti). Sono interessato a scoprire i combinatori di punti fissi (e la loro implementazione!) In grado di calcolare i punti fissi delle funzioni su questi tipi "esotici". In quanto cose come i numeri irrazionali hanno una rappresentazione decimale come sequenze infinite, sembra che questo calcolo debba essere valutato pigramente. Qualche di queste valutazioni pigre (Putative) producono buone approssimazioni ai veri punti fissi? Le mie lingue bersaglio sono Python e Clojure, ma certamente non mi dispiacerebbe vedere le implementazioni OCAML o Haskell).

Answer 1

Troverai tale funzione che calcola i punti fissi su Andrej Bauer Blog;Ad esempio programmi apparentemente impossibili e Ricerca infinita in tempo finito .Questo è per il caso in cui il punto fisso è effettivamente a una "distanza finita", in modo che venga raggiunto.

Alcuni dei punti fissi di cui stai parlando non sono di questo tipo, poiché sono davvero "infinitamente lontani".Questi sono i tipi di punti fissi che vengono utilizzati in analisi calcolabile .Fondamentalmente la teoria c'è tutto su come ottenere buone approssimazioni al punto fisso.