# CSCE 314: Programming Languages

# Assignment 5

## Objective

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.

## Instructions

- 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

#### Displaying trees

Make `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`

as

mytree = Branch "A" (Branch "B" (Leaf (1::Int)) (Leaf (2::Int))) (Leaf (3::Int))when you input

`mytree`

in the command line, the screen outputs something like
"A" "B" 1 2 3

#### Traversing trees

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 `c`

, and
the second function maps the values stored in the branching nodes to type
`c`

, thus, resulting in a list
of type `[c]`

.

## 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 `3`

and `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 `x`

and `y`

, determine whether it is possible to
make exactly `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 `x`

, `y`

and `z`

as inputs and outputs "True" if `z`

is measurable using `x`

and `y`

; otherwise, output "False".

measureWater :: Int -> Int -> Int -> Bool

Here is an example of the function being called:

*Main> measureWater 3 5 2 True

### Acknowledgement

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.