È possibile utilizzare le funzioni a punto fisso sui polinomi?

Question

Stavo pensando a un modo per rappresentare i numeri algebrici in Haskell come un flusso di approssimazioni. Probabilmente potresti farlo con qualche algoritmo di ricerca delle radici. Ma non è divertente. Quindi è possibile aggiungere x al polinomio, riducendo il problema alla ricerca di punti fissi.

Quindi, se si dispone di una funzione in Haskell come

f :: Double -> Double 
f x = x^2 + x 

io non capisco perché concettualmente correzione non funziona, vale a dire, posso facilmente verificare per me stesso che non funziona , ma non è lo zero vero punto fisso di f? Esiste un'altra funzione di punto fisso semplice (come nella dimensione della definizione) che funzionerebbe?

Answer 1

Qui è l'implementazione della funzione di correzione:

fix :: (a -> a) -> a 
fix f = let x = f x in x 

Non funziona per i tipi primitivi come Double. È destinato a tipi che presentano una struttura più complessa. Per esempio:

g :: Maybe Int -> Maybe Int 
g i = Just $ case i of 
    Nothing -> 3 
    Just _ -> 4 

Questa funzione opera con fix perché produce informazioni circa il suo risultato più velocemente di quanto si legge il suo input. in altre parole, la porzione Just è nota senza guardare allo i, il che consente di raggiungere un punto fisso.

Quando la vostra funzione è Double -> Double ed esamina il suo input, fix non funzionerà perché non c'è modo di valutare parzialmente uno Double.