-- SOME BASIC FUNCTIONS
-- --------------------
--
-- Note that two hyphens together mark the beginning
-- of a comment and are ignored by the interpretter.
--
-----------------------------------------------------


-- increment a number
inc n		= n + 1

-- add two numbers
add x y		= x + y


-- four ways to define Factorial
fact1 0		= 1
fact1 n		= n * fact1 (n - 1)

fact2 :: Int -> Int
fact2 n =
   case n of 0 -> 1
             _ -> n * fact2 (n - 1)

fact3 n =	if n == 0 then 1 else n * fact3(n-1)

fact4 n       
	| n < 0		= 0
	| n == 0	= 1
	| n > 0		= n * fact4(n-1)

fact5 n =       product [1..n]

-- using a partially applied (curried) enumFromTo,
-- which is the function behind the syntactic sugar: [1..n]  
-- which is equivalent to:  enumFromTo 1 n
--
-- plus function combination using the . operator: 
-- (f . g) x is equivalent to: f (g x)

fact6 = product . enumFromTo 1


-- find the n-th number in a Fibonacci sequence
fib :: Int -> Int
fib 1 = 1
fib 2 = 1
fib n = fib (n - 1) + fib (n - 2)


fib1 n = fibs !! n
    where fibs = 1 : 1 : zipWith (+) fibs (tail fibs)




-- SOME LIST FUNCTIONS
-----------------------------------------------------

-- length of a list
listlen [] = 0
listlen (x:xs) = 1 + listlen xs

-- reverse a list
myrev [] = []
myrev (x:xs) = myrev xs ++ [x]

-- find first instance of an item in a list
member a [] = []
member a (x:xs) 
	| a == x	= a:xs
	| otherwise	= member a xs

-- insert into an ordered list
insert x [] = [x]
insert x (y:ys) 
	| x < y		= x:y:ys
	| otherwise	=  y:insert x ys

-- an insertion sort
isort [] = []
isort (x:xs) = insert x:isort xs


palindrome x = (x == reverse x)



-- LIST COMPREHENSION
----------------------------------------------------------

-- create alist of all elements in a list that are less than five
lows lst = [x | x<- lst, x < 5]

-- create a list of all elements in a list that are even
evenmems lst = [z|z<-lst, (even z)]

-- quicksort using list comprehension
qsort [] = []
qsort (x:xs) = qsort [z|z<-xs,z<x] ++ [x] ++ qsort [z|z<-xs,z >= x]


-- get the first half of a list
firsthalf lst 
	= take half lst
	 where
	 half = length lst `div` 2

-- get the last half of a list
secondhalf lst
	= drop half lst
	where
	half = length lst `div` 2

-- merge two sorted lists
merge [] xs = xs
merge xs [] = xs
merge (x:xs) (y:ys)
	|  x<=y		= x : merge xs (y:ys)
	| otherwise	= y : merge (x:xs) ys

-- mergesort
mergesort xs
	| length xs < 2	= xs
	| otherwise 
		= merge
	 (mergesort (firsthalf xs))
	 (mergesort (secondhalf xs))


-- MORE ON LIST
----------------------------------------------------------

-- (inefficient) remove last element
butlast1 l = reverse (tail (reverse l))

-- same, but "point-free" function definition
butlast = reverse . tail . reverse


-- two versions for range
myrange i n = 
	if i == n 
	   then []
	   else i : myrange (i+1) n


myrange1 i n
	 | i == n    = []
	 | otherwise = myrange1 (i+1) n

-- wierd list comprehension based length, note '
length' xs = sum [1 | _ <- xs]


-- infinite lists
twos = 2 : twos

ignore1 a b = b

take 3 repeat " "


-- STRUCTURES AND LISTS OF STRUCTURES 
-----------------------------------------------------------
data Season = Spring | Summer | Fall | Winter


-- some type definitions
type Name = String
type SID = Int
type SRec = (SID,Name)
type Dbase = [SRec]

-- the database
initbase :: Dbase
initbase = []

-- add a record to the database
addrec sid name dataBase = (sid,name) : dataBase

-- a new database
newbase = addrec 123 "Ann" (addrec 234 "Bob" (addrec 345 "Ivy" (addrec 456 "Jim" initbase)))

-- search for a sid in a list of the form of newbase
find sid [] = []
find sid ((s,n):xs)
	|sid == s	= n
	|otherwise	= find sid xs

-- a better search if the database is sorted
goodfind sid [] = []
goodfind sid ((s,n):xs)
	| sid == s	= n
	| sid < s	= []
	| otherwise	= find sid xs

-- insert into an ordered list
linsert s n []	= [(s,n)]
linsert s n ((s1,n1):xs)
	| s<s1	= (s,n):(s1,n1):xs
	| otherwise = (s1,n1):linsert s n xs

-- e.g.  linsert "Tony" 333 newbase
--	==> [(123,"Ann"),(234,"Bob"),(333,"Tony"),(345,"Ivy"),(456,"Jim")]




-- TREES -- BINARY SEARCH TREE OPERATIONS
---------------------------------------------------------

-- a tree is either Nil or a Node with two trees

data Tree a = Nil | Node a (Tree a)(Tree a)
	deriving (Show)

data Thing1 a = Thing2

-- the depth of a tree is zero if it's Nil, otherwise 1 plus the
-- maximum height of its subtree 

depth Nil	= 0
depth (Node n t1 t2) = 1 + max (depth t1)(depth t2)


-- here's a binary search tree
aTree	= (Node 12
		(Node 10 Nil Nil)
		(Node 35
			(Node 27 Nil Nil) Nil))


-- inserting a value x into a BST

tinsert x Nil = (Node x Nil Nil)
tinsert x (Node y t1 t2)
	| x<y		= (Node y (tinsert x t1) t2)
	| otherwise	= (Node y t1 (tinsert x t2))


-- traversal of a BST producing an ordered list

inorder Nil	= []
inorder (Node x t1 t2) = inorder t1 ++ [x] ++ inorder t2

-- find a value in a BST

tfind x Nil		= False
tfind x (Node y t1 t2)
	| x==y		= True
	| x<y		= (tfind x t1)
	| otherwise	= (tfind x t2)

-- find maximum value in BST

tmax Nil	= error "Empty Tree"
tmax (Node x _ Nil)	= x
tmax (Node x _ t2)	= tmax t2