# Getting to Know Haskell

This assignment is due February 22 at 11:59 PM. Clone the Github repository and start working on `Assignment1.hs`

. Credit to Niki Vazou for making this assignment.

## Strings

In Haskell the `String`

data type is defined to be a list of `Char`

, so `String`

can be manipulated via list comprehension. For example, the below list comprehension is used to combine each possible adjectives with each possible noun.

[adj ++ " " ++ noun | adj <- ["lazy", "nasty"] , noun <- ["cat", "language"] ] = ["lazy cat","lazy language","nasty cat","nasty language"]

We recommend you read up on and use list comprehensions to define the following two functions. However, you can implement them anyway you like.

Complete the function

`removeUpper`

that removes all uppercase characters from its`String`

argument. (Hint: Use the library function`isUpper`

.)removeUpper "Hello World!" = "ello orld!"

Complete the function

`noIdent`

that removes any non-letter character of its`String`

argument to lower. A letter is one of the characters`a..z`

or`A..Z`

. (Hint: use the library function`elem`

.)noIdent "Hello World!" = "HelloWorld"

Use recursion to define the function

`isPrefixOf xs ys`

that returns`True`

if and only if`xs`

is prefix of`ys`

.isPrefixOf "Haskell" "I like Haskell" = False isPrefixOf "I like" "I like Haskell" = True

## Merge Sort

In this problem, you will implement the standard merge sort algorithm. The function `mergeSort`

splits the input list into halves, recursively sorts both halves, and merges the two sorted halves.

mergeSort :: [Int] -> [Int] mergeSort [] = [] mergeSort [x] = [x] mergeSort xs = merge (mergeSort ys) (mergeSort zs) where (ys,zs) = splitHalf xs

Define the function

`splitHalf`

that split the input list into two sublists. (Hint: You can use the function`splitAt`

.)splitHalf [1..4] == ([1,2],[3,4]) splitHalf [1..5] == ([1,2],[3,4,5])

Define the function

`merge`

that merges two sorted lists.merge [1,5,9] [2,8] == [1,2,5,8,9]

Your definition should satisfy the below type signature that reads as follows: The input lists contain elements of type

`a`

that satisfies the constraint`Ord`

. This constraint lets you use any of the standard following comparison operators on elements of the input lists.merge :: Ord a => [a] -> [a] -> [a]

Haskell defines the data type

`Ordering`

as follows.data Ordering = LT | EQ | GT

It represents less, equal, and greater comparison respectively. Moreover the library function

`compare`

is defined so the following hold.compare x y == LT <=> x < y compare x y == EQ <=> x == y compare x y == GT <=> x > y

Define the

`merge`

and`mergeSort`

functions to take an explicit comparison argument and use it to compare. That is, complete the definitions below so that:mergeBy compare xs ys = merge xs ys mergeSortBy compare xs == mergeSort xs

## Coloring

Let `Color`

be the red, green, blue or yellow color data type.

data Color = Red | Green | Blue | Yellow deriving (Eq, Show)

The above deriving annotation teaches Haskell how to compare colors and how to turn them to strings for printing. Similarly, the `Balkan`

data type defines the countries that belong in the `Balkan`

area.

data Balkan = Albania | Bulgaria | BosniaAndHerzegovina | Kosovo | Macedonia | Montenegro deriving (Eq, Show)

Two countries are adjacent when they share the same border. The below `adjacencies`

list captures all the Balkan adjacencies: `x`

is adjacent to `y`

when either `elem (x,y) adjacencies`

or `elem (y,x) adjacencies`

.

adjacencies :: [(Balkan,Balkan)] adjacencies = [ (Albania, Montenegro), (Albania, Kosovo), (Albania, Macedonia) , (Bulgaria, Macedonia), (BosniaAndHerzegovina, Montenegro) , (Kosovo, Macedonia), (Kosovo, Montenegro) ]

We call coloring a list of type `[(Balkan,Color)]`

that related each `Balkan`

country with a color. A coloring is good with respect to an adjacency matrix when every two adjacent countries have a different color. A coloring is complete with respect to an adjacency matrix when it colors every country in the matrix. Good colorings may be incomplete.

Write a function

`isGoodColoring adj coloring`

that returns`True`

if and only if the coloring list is good with respect to the input adjacency list.Define

`colorings`

to return all the good and complete colorings of the adjacency list adjacencies.

## Final Project

Get together with some of your classmates to form a final project group. Groups can have at most four people. Choose a project idea that you want to pursue. It doesn’t have to be a particularly original idea, but something that is of similar or greater complexity than our Sudoku program. Here are some starting ideas:

A program that can play a game like Connect Four, Gomoku, Poker, etc. against a user.

Any puzzle solver, other than Sudoku of course.

A maze generator and solver.

An implementation of a cool data structure, perhaps something from Okasaki’s book Purely Functional Data Structures.

A parser and interpreter for a small language, like Datalog or a basic Lisp.

You can really choose anything you want, although we may have recommendations if we think you’ve chosen something too easy or difficult.