# CSCE 314: Programming Languages

# Assignment 2

## Objective

In this assignment we'll get to writing more functions, especially more practice on recursive functions.

## Instructions

- This homework operates the same way at the previous one.

## Basic Haskell Drills

For each of the following problems, write: (a) A Haskell function type definition and (b) an actual Haskell function of the given name.

If the problem notes that it is recursive, use a recursive implementation (other questions could be recursive, also, and there could be non-recursive solutions).

`myReverse`

: given a list, reverse it. (recursive)`isElement`

: judge if a value is an element of a list. If it is, return True, else return False. (recursive)`duplicate`

: duplicate the elements of a list. For example,`duplicate [1,2]`

returns`[1,1,2,2]`

. (recursive)`removeDuplicate`

: given a sorted list, remove the duplicated elements in this list. (recursive)`rotate`

: rotate a list n places to the left, where n is an integer. For example,`rotate "abcde" 2`

returns`"cdeab"`

.`flatten`

: flatten a list of lists into a single list formed by concatenation. For example,`flatten [[1,2],[3,4],[5,6]]`

returns`[1,2,3,4,5,6]`

. (recursive)`isPalindrome`

: given a list, judge if it is a palindrome.`coprime`

: given two positive integer numbers, determine whether they are coprime. Two numbers are coprime if their greatest common divisor equals 1. Hint: Euclid's algorithm. (recursive)

## Aaah! (Easy)

When we go to see a doctor, the doctor always asks us to say "aaah". Sometimes, the doctor needs us to say "aaaaaah", but we are only able to say "aaah".
In that case, the doctor is unable to diagnose our disease, because the 'a's in
our "aaah" are fewer than his or her requirements. Now, write a Haskell
function called `seeDoctor`

to judge if the doctor can diagnose us
with our "aah". The input of the function consists of two strings. The first
string is the *"aaaah"* the doctor needs and the second string is the *"aah"* we
are able to say. Output "True" if
our *"aah"* meets the requirements of the doctor, and output "False"
otherwise.
The test should pass with a "True" only when lowercase 'a's and 'h's are
used, and each string contains a certain number of 'a's followed by a single
'h'.

seeDoctor:: String -> String -> Bool

## Water Gates (Medium)

There are *n* water gates in a reservoir that are initially closed. To adjust water in the reservoir, we open/close the water gates according to the
following rule: on the first day, we open all the gates. Then, on the second day, we close every second gate.
On the third day, we change the state of every third gate (open it if it's closed or close it if it's open) ... For the *i*th day, we change the state
of every *i* gate. Finally, for the *n*th day, we change the state of the last gate. Our question is, how many gates are open after n days?

Given n = 4. At first, the gates are[closed, closed, closed, closed]. After the first day, the gates are[open, open, open, open]. After the second day, the gates are[open, closed, open, closed]. After the third day, the gates are[open, closed, closed, closed]. After the fourth day, the gates are[open, closed, closed, open]. So you should return 2, because there are two gates open.

Write a Haskell function called `waterGate`

that computes how many of *n* water gates are open after *n* days.

waterGate :: Int -> Int

## Goldbach's other conjecture (Hard)

Goldbach's other conjecture: Christian Goldbach once proposed that every odd composite number can be written as the sum of a prime and twice a square. For example,

9 = 7 + 2×1^2

15 = 7 + 2×2^2

21 = 3 + 2×3^2

25 = 7 + 2×3^2

27 = 19 + 2×2^2

33 = 31 + 2×1^2

However, this conjecture turns out to be false. Write a Haskell function called `goldbachNum`

to find the smallest odd composite that does not match Goldbach's other conjecture.

`goldbachNum :: Int `

### Checking your answers

The collection of tests for this assignment are here.
Note that, as before, to use these tests, you need to have `HUnit`

installed in your haskell environment.

### Acknowledgements

Basic Haskell Drills are adapted from Dr. Dylan Shell and Dr. Hyunyoung Lee's previous CSCE 314 materials and "H-99: Ninety-Nine Haskell Problems".

Aaah! problem is adapted from 2012 Nordic Collegiate Programming Contest, October 6, problem A.

Water Gates problem is adapted from the bulb switcher problem at Leetcode, problem 319.

Goldbach's other conjecture problem is from Project Euler, problem 46.