23 lines
665 B
Haskell
23 lines
665 B
Haskell
module DenseNat where
|
|
|
|
data Digit = Zero | One deriving (Show, Ord, Eq, Enum)
|
|
|
|
type DenseNat = [Digit] -- increasing order of significance
|
|
|
|
inc :: DenseNat -> DenseNat
|
|
inc [] = [One]
|
|
inc (Zero : ds) = One : ds
|
|
inc (One : ds) = Zero : inc ds -- carry
|
|
|
|
dec :: DenseNat -> DenseNat
|
|
dec [One] = []
|
|
dec (One : ds) = Zero : ds
|
|
dec (Zero : ds) = One : dec ds -- borrow
|
|
|
|
add :: DenseNat -> DenseNat -> DenseNat
|
|
add ds [] = ds
|
|
add [] ds = ds
|
|
add (d : ds1) (Zero : ds2) = d : add ds1 ds2
|
|
add (Zero : ds1) (d : ds2) = d : add ds1 ds2
|
|
add (One : ds1) (One : ds2) = Zero : inc (add ds1 ds2) -- carry
|