module HW3 where

import Hugs.Prelude hiding (gcd,unzip,reverse)

-- ############################################

-- QUESTION 4.9

-- f(n) =return the max of f(0),f(1)......f(n-1),f(n)

-- ############################################

f :: Int->Int

f n

| n==0 =0

| n>0 = max (f(n-1)) n

-- script modification

f2:: Int->Int

f2 n

| n==0 =0

| n==1 =44

| n==2 =17

| n>0 = max (f2(n-1)) n

| otherwise=0

-- ############################################

-- fibAlt

-- ############################################

fib :: Int -> Int

fib n

| n==0 = 0

| n==1 = 1

| n>1 = fib (n-2) + fib (n-1)

fibAlt :: Int -> Int

fibAlt n

| odd n = negate(fib n)

| otherwise = fib n

{- ############################################

QUESTION 4.10

############################################-}

f3::Int->Int

f3 n

| n>=0 && n<=10 = 10

| otherwise= 0

lookZero:: Int->Bool

lookZero n

| n==0 = (f3(0)==0)

| otherwise= (f3(n)==0) || lookZero(n-1)

-- ########################################

-- QUESTION 4.13

-- ########################################

myGcd :: Int->Int->Int

myGcd u v

| u==0 =v

| even(u) && even(v) =2*(myGcd (div u 2) (div v 2) )

| even(u) = myGcd (div u 2) v

| even(v) = myGcd u (div v 2)

| u>=v = myGcd (div (u-v) 2) v

| otherwise = myGcd u (div (v-u) 2)

{- ############################################

QUESTION 4.14

2^n and n=2*m

if (n is even) 2^n=(2^m)^2

if (n is odd ) 2^n=2^(2*m+1)=(2^m)^2*2

############################################-}

isOdd, isEven :: Int->Bool

isOdd n

| n<=0 = False

| otherwise =isEven(n-1)

isEven n

| n<0 =False

| n==0 =True

| otherwise =isOdd(n-1)

powTwo::Int->Int

powTwo n

| n==0 =1

| n==1 =2

| isEven n = powTwo(div n 2)*powTwo(div n 2)

| isOdd n = 2*powTwo(div n 2)*powTwo(div n 2)

| otherwise =0 -- when n is negative

-- ############################################

-- QUESTION 5.2 "orderTriple"

-- ############################################

between :: Int -> Int -> Int -> Bool

between x y z

| x<=y && y<=z =True

| otherwise =False

minThree :: Int -> Int -> Int -> Int

minThree x y z = (x `min` y) `min` z

maxThree :: Int -> Int -> Int -> Int

maxThree x y z = (x `max` y) `max` z

middleNumber :: Int -> Int -> Int -> Int

middleNumber x y z

| between y x z = x

| between z x y = x

| between x y z = y

| between z y x = y

| between x z y = z

| between y z x = z

orderTriple:: (Int,Int,Int)-> (Int,Int,Int)

orderTriple (a,b,c)=( (minThree a b c), (middleNumber a b c), (maxThree a b c) )

{- ############################################

QUESTION 5.10

############################################-}

-- or a boolean list

orp :: [Bool]->Bool

orp [] = False

orp (x:xs) = x || orp xs

-- make a list of booleans where numbers can divide n without fractional part

modList::Int->[Bool]

modList n=[ (mod n ls)==0 | ls<-[2..floor (sqrt (fromInt n))]]

isPrime:: Int->Bool

isPrime n

| n<=0 =False

| n==1 =False

| n==2 =True

| n==3 =True

| otherwise=not(orp (modList n) )

-- FDIV:

-- checks the numbers from i to n

-- if the i>=n then return empty list

-- if (n/i) is an integer add [i] to the list, and check i+1 ...

-- otherwise, check i+1

fdiv::Int->Int->[Int]

fdiv i n

| i>=n=[]

| (mod n i)==0 =[i]++(fdiv (i+1) n)

| otherwise=fdiv (i+1) n

-- call Fdiv

divisors::Int->[Int]

divisors n=[1] ++ (fdiv 2 n) ++ [n];

{- ############################################

QUESTION 5.11

############################################-}

matches::Int->[Int]->[Int]

matches n lst

| lst==[] = []

| otherwise=[ el | el<-lst, el==n ]

countNum::Int->[Int]->Int

countNum _ []=0

countNum n (x:xs)

| n==x =1+ (countNum n xs)

| otherwise = (countNum n xs)

matches2 :: Int->[Int]->[Int]

matches2 n list

| countNum n list==0 =[]

| otherwise=replicate (countNum n list) n

{- ############################################

QUESTION 7.6

exactly like "countNum" in 5.11

############################################-}

elemNum::Int->[Int]->Int

elemNum _ []=0

elemNum n (x:xs)

| n==x =1+ elemNum n xs

| otherwise = elemNum n xs

{- ############################################

QUESTION 7.7

############################################-}

unique :: [Int]->[Int]

unique []=[]

unique ls=[el | el<-ls, (countNum el ls)==1]

{- ############################################

QUESTION 7.8

############################################-}

unzip2::[(Int,Int)] -> ([Int],[Int])

unzip2 ((a,b):xs) = (a:as,b:bs) where (as,bs) = unzip xs

reverse2::[Int]->[Int]

reverse2 []=[]

reverse2 (x:xs) =(reverse2 xs) ++ [x]

{- ############################################

QUESTION 7.9

############################################-}

ins::Int->[Int]->[Int]

ins x []=[x]

ins x (y:ys)

| x<=y =x:(y:ys)

| otherwise = y : ins x ys

iSort::[Int]->[Int]

iSort []=[]

iSort (x:xs)=ins x (iSort xs)

getMin::[Int]->Int

getMin ls=head (iSort ls)

getMax::[Int]->Int

getMax ls=last (iSort ls)

--without using isort, by using Quicksort

qkSort::[Int]->[Int]

qkSort []=[]

qkSort (x:xs)= qkSort[ el | el<-xs, el<=x ] ++ [x] ++ qkSort[ el | el<-xs, el>x ]

getMin2::[Int]->Int

getMin2 ls=head (qkSort ls)

getMax2::[Int]->Int

getMax2 ls=last (qkSort ls)

-- without using any sort

getMin3::[Int]->Int

getMin3 (x:xs)

| xs==[]=x

| otherwise=getMin3 ([el | el<-xs, el < x] ++ [x])

getMax3::[Int]->Int

getMax3 (x:xs)

| xs==[]=x

| otherwise=getMax3 ([el | el<-xs, el > x] ++ [x])

{- ############################################

QUESTION 7.11

modified "ins"

iSort2 now sort in DESCENDING ORDER

iSort2 [2,1,4,1,4] = [4,2,1]

############################################-}

ins2::Int->[Int]->[Int]

ins2 x []=[x]

ins2 x (y:ys)

| x==y =(y:ys)

| x>y =x:(y:ys)

| otherwise = y : ins2 x ys

iSort2::[Int]->[Int]

iSort2 []=[]

iSort2 (x:xs)=ins2 x (iSort2 xs)

{- ############################################

QUESTION 7.13

Sort Pairs lexicographically

############################################-}

insT::(Int,Int)->[(Int,Int)]->[(Int,Int)]

insT (a,b) []=[(a,b)]

insT (a,b) ((x,y):xs)

| a<x =(a,b):((x,y):xs)

| a==x && b<=y =(a,b):((x,y):xs)

| otherwise =(x,y) : insT (a,b) xs

sortT::[(Int,Int)]->[(Int,Int)]

sortT [] =[]

sortT (x:xs) =insT x (sortT xs)