Posts Tagged ‘convert’

Programming Praxis – Big Numbers: Input And Output

June 14, 2011

In today’s Programming Praxis exercise, our task is to write functions to convert Big Numbers to and from strings. Let’s get started, shall we?

To convert from a string, we simply convert each digit to the correct value, multiplying them by the base as we go along.

readBase :: (Num a, Enum a) => a -> String -> a
readBase b xs       = foldl (\a x -> b * a + val x) 0 xs where
val d = maybe (error "unrecognized digit") id . lookup d \$ zip
(['0'..'9'] ++ ['A'..'Z'] ++ ['a'..'z']) [0..]

To convert to a string, we divide by the base until we reach zero. The remainders form the digits of the output.

showBase :: Integral a => a -> a -> String
showBase b n = if n < 0 then '-' : showBase b (abs n) else
map (digit . snd) \$ m : reverse ms  where
((_:ms), (m:_)) = span ((> 0) . fst) \$ iterate (flip divMod b . fst) (n, 0)
digit d = maybe undefined id . lookup d . zip [0..] \$
['0'..'9'] ++ ['A'..'Z'] ++ ['a'..'z']

While we’re at it let’s also make BigNum an instance of Read and Show, the typeclasses that normally handle conversion to and from strings.

split ('-':xs) = first ('-':) \$ split xs
split xs       = span (`elem` ['0'..'9'] ++ ['A'..'Z'] ++ ['a'..'z']) xs

instance Show BigNum where
show = showBase 10

Some tests to see if everything is working properly:

main :: IO ()
main = do print \$ readBase 10 "1234"   == ( 1234 :: BigNum)
print \$ readBase 10 "-1234"  == (-1234 :: BigNum)
print \$ readBase  2 "101010" == (   42 :: BigNum)
print \$ read "-1234"         == (-1234 :: BigNum)
print \$ showBase 10 ( 1234 :: BigNum) ==   "1234"
print \$ showBase 10 (-1234 :: BigNum) ==  "-1234"
print \$ showBase  2 (   42 :: BigNum) == "101010"
print \$ show        (-1234 :: BigNum) ==  "-1234"