-- Informatics 2A Assignment 1, Nov 2015
-- MH test program 5

-- A longer program, just for fun.
-- Conversion of integers to binary sequences, represented using Integer->Bool

-- Logarithms to base 2, rounded down. Pretend log2 0 = 0.

log2' :: Integer -> Integer -> Integer -> Integer ;
log2' n i j = if j+j <= n then log2' n (i+1) (j+j) else i ;

log2 :: Integer -> Integer ;
log2 n = log2' n 0 1 ;

-- Powers of 2

double :: Integer -> Integer ;
double n = n+n ;

twoTo :: Integer -> Integer ;
twoTo n = if n==0 then 1 else double(twoTo(n-1)) ;

-- Conversion to binary
-- Here n < 2^d is a number to be converted to d binary digits,
-- which are consed onto f, an already computed list of more significant digits

cons :: Bool -> (Integer -> Bool) -> (Integer -> Bool) ;
cons b f i = if i==0 then b else f(i-1) ;

toBin' :: Integer -> Integer -> (Integer -> Bool) -> (Integer -> Bool) ;
toBin' n d rest = 
     if d==0 then rest
     else if twoTo (d-1) <= n then toBin' (n-twoTo(d-1)) (d-1) (cons True rest)
     else toBin' n (d-1) (cons False rest) ;

zero :: Integer -> Bool ;
zero i = False ;

toBin :: Integer -> (Integer -> Bool) ;
toBin n = toBin' n (log2 n + 1) zero ; 

-- Example:

bin13 :: Integer -> Bool ;
bin13 = toBin 13 ;


-- Test whether first five binary digits of f agree with binary representation of thirteen

and :: Bool -> Bool -> Bool ;
and a b = if a then b else False ;

not :: Bool -> Bool ;
not a = if a then False else True ;

isBin13 :: (Integer -> Bool) -> Bool ;
isBin13 f = and (f 0) (and (not (f 1)) (and (f 2) (and (f 3) (not (f 4))))) ;

-- Test expression: isBin13 bin13 
-- Type should be:  Bool
-- Value should be: True