What is this algorithm for converting strings into numbers called?
- by CodexArcanum
I've been doing some work in Parsec recently, and for my toy language I wanted multi-based fractional numbers to be expressible. After digging around in Parsec's source a bit, I found their implementation of a floating-point number parser, and copied it to make the needed modifications.
So I understand what this code does, and vaguely why (I haven't worked out the math fully yet, but I think I get the gist). But where did it come from? This seems like a pretty clever way to turn strings into floats and ints, is there a name for this algorithm? Or is it just something basic that's a hole in my knowledge? Did the folks behind Parsec devise it?
Here's the code, first for integers:
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)
}
So the basic idea here is that digits contains the string representing the whole number part, ie "192". The foldl converts each digit individually into a number, then adds that to the running total multiplied by the base, which means that by the end each digit has been multiplied by the correct factor (in aggregate) to position it.
The fractional part is even more interesting:
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)
Same general idea, but now a foldr and using repeated division. I don't quite understand why you add first and then divide for the fraction, but multiply first then add for the whole. I know it works, just haven't sorted out why.
Anyway, I feel dumb not working it out myself, it's very simple and clever looking at it. Is there a name for this algorithm? Maybe the imperative version using a loop would be more familiar?
