Posts Tagged ‘show’

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) = - readBase b xs
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.

instance Read BigNum where
    readsPrec _ = return . first (readBase 10) . split where
        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"