question4.hs

-- Homework 2
-- Abstract transfer function for unsigned subtraction for
-- 4-bit abstract values in the interval abstract domain

-- run command: `ghci question4.hs`

import Data.List
import Prelude hiding (subtract)

type Interval = (Integer, Integer)

intervalToSet :: Interval -> [Integer]
intervalToSet (x, y) = [x..y]

fourBitsSub :: Integer -> Integer -> Integer
fourBitsSub x y = if x >= y then x - y else 15 - (y - x) + 1

inRange :: Interval -> Bool
inRange (x,y) = x >=0 && x <= 15 && y >= 0 && y <= 15

subtract :: Interval -> Interval -> [Integer]
subtract x y | inRange x && inRange y = nub [fourBitsSub a b | a <- intervalToSet x, b <- intervalToSet y]
             | otherwise = error "input interval overflow"

-- some tests
test1 = subtract (0,15) (0,15)   -- top
test2 = subtract (0,3) (0,0)     -- [0,1,2,3]
test3 = subtract (5,6) (1,2)     -- [3,4,5]