In today’s Programming Praxis exercise, our task is to implement the basics of a library for big numbers. Let’s get started, shall we?

A quick import:

import Data.List

We could represent a big number as a plain list like the Scheme version does. Using a custom data structure, however, has the advantage of being able to make it an instance of the standard numeric classes, which means shorter function names and easier literals. We also store the number of digits separately because I find it a bit cleaner.

data BigNum = B Int [Int] deriving (Eq, Show)

We’re using 1000 as our base for now.

base :: Integer base = 1000

The Num class gives us some of the required functions. Since addition and multiplication haven’t been implemented yet the compiler will throw some warnings.

instance Num BigNum where negate (B l ds) = B (-l) ds abs (B l ds) = B (abs l) ds signum (B l _) = fromIntegral $ signum l fromInteger n | n < 0 = negate $ fromInteger (-n) | otherwise = B (length ds) (map fromIntegral ds) where ds = tail $ f (n,0) f (0,m) = [m] f (d,m) = m : f (divMod d base)

I personally don’t see much use for three separate functions for the sign of a number, since you can either use signum or the appropriate comparsion, but we’ll stick to the assignment.

positive, negative, zero :: (Num a, Ord a) => a -> Bool positive = (> 0) negative = (< 0) zero = (== 0)

If we make BigNum an instance of the Integral class we could use the default even and odd functions, but this requires implementing modulo arithmetic. We’ll use these for now until we have to do so in a following exercise.

bigOdd, bigEven :: BigNum -> Bool bigEven (B l ds) = l == 0 || even (head ds) bigOdd = not . bigEven

The Integral class also has a toInteger function, but for now we’ll use a separate function.

fromBig :: BigNum -> Integer fromBig (B _ ds) = foldr (\x a -> fromIntegral x + base * a) 0 ds

Here’s another advantage of using the standard type classes: we only need to implement the compare function to get all the others for free.

instance Ord BigNum where compare (B l1 ds1) (B l2 ds2) = case compare l1 l2 of EQ -> maybe EQ id . find (/= EQ) . reverse $ zipWith compare ds1 ds2 c -> c

Time for a whole bunch of tests.

main :: IO () main = do let a = 12345678 let b = -87654321 print $ 0 == B 0 [] print $ 1 == B 1 [1] print $ (-1) == B (-1) [1] print $ a == B 3 [678,345,12] print $ b == B (-3) [321,654,87] print $ fromBig a == 12345678 print $ fromBig (abs b) == 87654321 print $ abs a == a print $ positive a print $ negative b print $ zero (0 :: BigNum) print $ bigEven a print $ bigOdd b print $ b /= a print $ b < a

Looks like everything is working properly.

Tags: big, bonsai, code, Haskell, kata, numbers, praxis, programming

## Leave a Reply