module SparseNat where

type SparseNat = [Int] -- increasing list of powers of 2

carry :: Int -> SparseNat -> SparseNat
carry w []     = [w]
carry w ws@(w' : rest)
   | w < w'    = w : ws
   | otherwise = carry (2 * w) rest

borrow :: Int -> SparseNat -> SparseNat
borrow w ws@(w' : rest)
   | w < w'    = rest
   | otherwise = w : borrow (2 * w) ws

inc :: SparseNat -> SparseNat
inc = carry 1

dec :: SparseNat -> SparseNat
dec = borrow 1

add :: SparseNat -> SparseNat -> SparseNat
add ws [] = ws
add [] ws = ws
add m@(w1 : ws1) n@(w2 : ws2)
   | w1 < w2   = w1 : add ws1 n
   | w2 < w1   = w2 : add m ws2
   | otherwise = carry (2 * w1) (add ws1 ws2)