-- # Software Tools for Discrete Mathematics
module Stdm13 where

-- # Chapter 13.  Discrete Mathematics in Circuit Design
class Signal a where
  inv :: a -> a
  and2, or2, xor :: a -> a -> a

instance Signal Bool where
  inv False = True
  inv True = False
  and2 = (&&)
  or2 = (||)
  xor False False = False
  xor False True = True
  xor True False = True
  xor True True = False

-- halfAdd :: Signal a => a -> a -> (a,a)
halfAdd a b = (and2 a b, xor a b)

fullAdd :: (Signal a) => (a, a) -> a -> (a, a)
fullAdd (a, b) c = (or2 w y, z)
  where
    (w, x) = halfAdd a b
    (y, z) = halfAdd x c

-- halfAdd False False
-- halfAdd False True
-- halfAdd True  False
-- halfAdd True  True
--
-- fullAdd (False, False) False
-- fullAdd (False, False) True
-- fullAdd (False, True)  False
-- fullAdd (False, True)  True
-- fullAdd (True,  False) False
-- fullAdd (True,  False) True
-- fullAdd (True,  True)  False
-- fullAdd (True,  True)  True

add4 :: (Signal a) => a -> [(a, a)] -> (a, [a])
add4 c [(x0, y0), (x1, y1), (x2, y2), (x3, y3)] =
  (c0, [s0, s1, s2, s3])
  where
    (c0, s0) = fullAdd (x0, y0) c1
    (c1, s1) = fullAdd (x1, y1) c2
    (c2, s2) = fullAdd (x2, y2) c3
    (c3, s3) = fullAdd (x3, y3) c

-- Example: addition of 3 + 8
--    3 + 8
--    =   0011   (  2+1 =  3)
--      + 1000   (    8 =  8)
--    =   1011   (8+2+1 = 11)
-- Calculate this by evaluating
--    add4 False [(False,True),(False,False),(True,False),(True,False)]
-- The expected result is
--    (False, [True,False,True,True])

mscanr :: (b -> a -> (a, c)) -> a -> [b] -> (a, [c])
mscanr f a [] = (a, [])
mscanr f a (x : xs) =
  let (a', ys) = mscanr f a xs
      (a'', y) = f x a'
   in (a'', y : ys)

rippleAdd :: (Signal a) => a -> [(a, a)] -> (a, [a])
rippleAdd c zs = mscanr fullAdd c zs

-- Example: addition of 23+11
--    23 + 11
--    =   010111   (16+4+2+1 = 23)
--      + 001011   (   8+2+1 = 11) with carry input = 0
--    =   100010   (    32+2 = 34) with carry output = 0
-- Calculate with the circuit by evaluating
--    rippleAdd False [(False,False),(True,False),(False,True),
--                   (True,False),(True,True),(True,True)]
-- The expected result is
--    (False, [True,False,False,False,True,False])