Recentemente ho lavorato un po 'su Parsec, e per il mio linguaggio giocattolo volevo che fossero espressi numeri frazionari multi-base. Dopo aver scavato un po 'nella fonte di Parsec, ho trovato la loro implementazione di un parser in virgola mobile e l'ho copiato per apportare le modifiche necessarie.
Quindi capisco cosa fa questo codice, e vagamente perché (non ho ancora elaborato completamente la matematica, ma penso di aver capito il senso). Ma da dove è venuto? Questo sembra un modo abbastanza intelligente per trasformare le stringhe in float e int, c'è un nome per questo algoritmo? O è solo qualcosa di fondamentale che è un buco nella mia conoscenza? La gente dietro a Parsec l'ha ideata?
Ecco il codice, prima per i numeri interi:
number' :: Integer -> Parser Integer
number' base =
do { digits <- many1 ( oneOf ( sigilRange base ))
; let n = foldl (\x d -> base * x + toInteger (convertDigit base d)) 0 digits
; seq n (return n)
}
Quindi l'idea di base è che digits contenga la stringa che rappresenta l'intera parte del numero, ovvero "192" . Il foldl converte ogni cifra singolarmente in un numero, quindi la aggiunge al totale parziale moltiplicato per la base, il che significa che alla fine ogni cifra è stata moltiplicata per il fattore corretto (in aggregato) per posizionarla.
La parte frazionaria è ancora più interessante:
fraction' :: Integer -> Parser Double
fraction' base =
do { digits <- many1 ( oneOf ( sigilRange base ))
; let base' = fromIntegral base
; let f = foldr (\d x -> (x + fromIntegral (convertDigit base d))/base') 0.0 digits
; seq f (return f)
La stessa idea generale, ma ora foldr e utilizzo della divisione ripetuta. Non capisco perché prima si aggiunge e poi si divide per la frazione, ma prima si moltiplica e poi si aggiunge per il tutto. So che funziona, ma non ho risolto il motivo.
Ad ogni modo, mi sento stupido a non lavorarci da solo, è molto semplice e intelligente guardarlo. C'è un nome per questo algoritmo? Forse la versione imperativa che utilizza un ciclo sarebbe più familiare?