CPSC 3400 HW4 Final
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117
(*
Hope Crosier
CPSC 3400
HW 4
All of the code you turn in must have been written by you without immediate
reference to another solution to the problem you are solving. That means that you can look at
other programs to see how someone solved a similar problem, but you shouldn't have any code
written by someone else visible when you write yours (and you shouldn't have looked at a
solution just a few seconds before you type!). You should compose the code you write based on
your understanding of how the features of the language you are using can be used to implement
the algorithm you have chosen to solve the problem you are addressing. Doing it this way is
"real programming" - in contrast to just trying to get something to work by cutting and pasting
stuff you don't actually understand. It is the only way to achieve the learning objectives of the
course.
I attest to the statement above
*)
///PART ONE
///Given a length, width and height, computes the volume as a float
let cubeVolume (x,y,z) = float x * y * z
///goes through a list of tuples and creates a list of their volumes
let rec volumelist list =
if list = []
then []
else
let hd :: tl = list
// compute volume of head values and append to list
cubeVolume(hd) :: volumelist tl
///goes through a list of volumes and finds the max volume
let maxVolume list =
let rec loop max = function
| [] -> max
// if hd volume is greater than max, send hd as new max
// otherise continue with previous max
| hd :: tl -> loop (if hd > max then hd else max) tl
loop 0.0 list
///calls the functions above on a list to correctly get the max cube volume
let maxCubeVolume list = maxVolume (volumelist (list))
/// PART TWO
/// Takes in a key x and a head value (y,z) to see if x and y are equal
let checkChar (x: string) ((y,z): string*int) =
if x = y then true else false
/// Takes in a head value (a,b) and returns only b
let getChar ((a,b): string*int) = b
/// Takes in a key value x and a list of (string*int) values and gets int values
/// of list items that match the given key
let rec getListMatches x list =
if list = []
then []
else
let hd :: tl = list
// see if current hd values match key
if (checkChar x hd)
then
// get the integer value from current hd and append to list
getChar hd :: getListMatches x tl
// otherwise ignore currnet hd and continue to rest of list
else getListMatches x tl
/// Function to call getListMatches and sort the resulting list
let findMatches x list =
let matchlist = getListMatches x list
// sort the integers that match the key from previous function call
let result = List.sort matchlist
result
/// PART THREE
/// Tree definition for problem 3
type BST =
| Empty
| TreeNode of int * BST * BST
/// takes a value and and a tree to insert a new node with passed in value to
let rec insert value tree =
match tree with
// if tree is empty, add node with no following nodes
| Empty -> TreeNode(value, Empty, Empty)
// if tree has existsing node and new node value is less than previous node
// then insert it on the left side of the existing node
| TreeNode(oldVal, node1, node2) when value < oldVal -> TreeNode(oldVal, insert value node1, node2)
// will recursively go until right spot is found
// if tree has existing node and new node value is greater than previous node
// then insert it on the right side of the existing node
| TreeNode(oldVal, node1, node2) when value > oldVal -> TreeNode(oldVal, node1, insert value node2)
// will recursively go until right spot is found
// when value = oldVal, no insertion will take place since it already exists in the tree
| _ -> tree
/// Recursively searches a tree to see if the provided value exists within a node
let rec contains value = function
// Base case when value has not been found or when tree is empty
| Empty -> false
// Goes through and searches tree depending on what value of current node is
| TreeNode(compareVal, node1, node2) ->
if value = compareVal then true
elif value < compareVal then contains value node1 // search left
else contains value node2 // search right
/// given a function that returns true or false, counts the number of nodes that satisfy that function
let rec count func = function
| Empty -> 0
| TreeNode(value, node1, node2) -> // recursively sum all the counts from each side of tree
(count func node1) + (count func node2) + (if (func value) then 1 else 0)
/// counts the number of nodes in a tree whose value is even
let evenCount tree =
let result = count (fun value -> value % 2 = 0) tree
result
Fsharp
INFO