29 lines
656 B
Haskell
29 lines
656 B
Haskell
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)
|