In this assignment you'll work with more advanced data types. Also there is another problem for which higher-order functions can be fruitfully employed.
- Because some of the questions are to produce attractive looking output, these won't be evaluable using test functions. Use your judgement in these cases!
Tree traversal and its application
Consider the following data type.
data Tree a b = Branch b (Tree a b) (Tree a b) | Leaf a
Tree an instance of
Show. Do not use
deriving; define the instance yourself. Make the output look somewhat nice (e.g., indent nested branches). For example, if you define
mytree = Branch "A" (Branch "B" (Leaf (1::Int)) (Leaf (2::Int))) (Leaf (3::Int))when you input
mytreein the command line, the screen outputs something like
"A" "B" 1 2 3
Traverse the tree in the given order with a corresponding Haskell function, which collects the values from the tree nodes into a list:
preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
postorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
inorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
Note: The values in the tree cannot be collected to a list as such because the values on
the leaves are of a different type than the values on the branching nodes. Thus
each of these functions takes two functions as arguments: The first function
maps the values stored in the leaves to some common type
the second function maps the values stored in the branching nodes to type
c, thus, resulting in a list
Die Hard 3: Jugs Problem
In the film "Die Hard 3", to stop a bomb exploding in a park, the heros John McClain and Zeus have to solve a "Jugs Problem"
proposed by the evil Peter Krieg: given two jugs with capacities
5 gallons, make exactly
4 gallons from these two jugs.
In fact, the "Jugs Problem" can be generalized as follows: given two jugs with non-negative integer capacities
y, determine whether it is possible to
z units of water using those two jugs. The
z units of water must be contained within one or both jugs in the end.
Note: We assume there is an supply of water available. You can fill any of the jugs completely, empty any of the jugs, or transfer water from one jug into another till the other jug is full or the first jug itself is empty. The jugs are oddly shaped, so filling up exactly "half" (or some fractional bit) of the jug is impossible.
Implement a Haskell function that takes
z as inputs and outputs "True" if
z is measurable using
y; otherwise, output "False".
measureWater :: Int -> Int -> Int -> Bool
Here is an example of the function being called:
*Main> measureWater 3 5 2 True
Tree traversal: Dr. Dylan Shell and Dr. Hyunyoung Lee's previous CSCE 314 assignments
Jugs Problem is adapted from Leetcode Problem 365. You can watch the plot in Die Hard 3 here .
Check your answers
The test cases for this assignment are here. You may, of course, have some extra white space in your tree traversals, but this should be helpful to ensure you're on track.