Getting to Know Haskell

This assign­ment is due Feb­ru­ary 22 at 11:59 PM. Clone the Github repos­i­tory and start work­ing on Assign­ment1.hs. Credit to Niki Vazou for mak­ing this assign­ment.

In Haskell the String data type is defined to be a list of Char, so String can be manip­u­lated via list com­pre­hen­sion. For exam­ple, the below list com­pre­hen­sion is used to com­bine each pos­si­ble adjec­tives with each pos­si­ble noun.

[adj ++ " " ++ noun | adj <- ["lazy", "nasty"]
                    , noun <- ["cat", "lan­guage"] ]
  = ["lazy cat","lazy lan­guage","nasty cat","nasty lan­guage"]

We rec­om­mend you read up on and use list com­pre­hen­sions to define the fol­low­ing two func­tions. How­ever, you can imple­ment them any­way you like.

1. Com­plete the func­tion remove­Upper that removes all upper­case char­ac­ters from its String argu­ment. (Hint: Use the library func­tion is­Upper.)

   remove­Upper "Hello World!" = "ello orld!"
   

2. Com­plete the func­tion no­Ident that removes any non-let­ter char­ac­ter of its String argu­ment to lower. A let­ter is one of the char­ac­ters a..z or A..Z. (Hint: use the library func­tion elem.)

   no­Ident "Hello World!" = "Hello­World"
   

3. Use recur­sion to define the func­tion is­Pre­fix­Of xs ys that returns True if and only if xs is pre­fix of ys.

   is­Pre­fix­Of "Haskell" "I like Haskell" = False
   is­Pre­fix­Of "I like" "I like Haskell" = True
   

In this prob­lem, you will imple­ment the stan­dard merge sort algo­rithm. The func­tion merge­Sort splits the input list into halves, recur­sively sorts both halves, and merges the two sorted halves.

merge­Sort :: [Int] -> [Int]
merge­Sort []  = []
merge­Sort [x] = [x]
merge­Sort xs  = merge (merge­Sort ys) (merge­Sort zs)
  where
  (ys,zs)     = split­Half xs

1. Define the func­tion split­Half that split the input list into two sub­lists. (Hint: You can use the func­tion split­At.)

   split­Half [1..4] == ([1,2],[3,4])
   split­Half [1..5] == ([1,2],[3,4,5])
   

2. Define the func­tion merge that merges two sorted lists.

   merge [1,5,9] [2,8] == [1,2,5,8,9]
   

   Your def­i­n­i­tion should sat­isfy the below type sig­na­ture that reads as fol­lows: The input lists con­tain ele­ments of type a that sat­is­fies the con­straint Ord. This con­straint lets you use any of the stan­dard fol­low­ing com­par­i­son oper­a­tors on ele­ments of the input lists.

   merge :: Ord a => [a] -> [a] -> [a]
   

3. Haskell defines the data type Order­ing as fol­lows.

   data Order­ing = LT | EQ | GT
   

   It rep­re­sents less, equal, and greater com­par­i­son respec­tively. More­over the library func­tion com­pare is defined so the fol­low­ing hold.

   com­pare x y == LT <=> x <  y
   com­pare x y == EQ <=> x == y
   com­pare x y == GT <=> x >  y
   

   Define the merge and merge­Sort func­tions to take an explicit com­par­i­son argu­ment and use it to com­pare. That is, com­plete the def­i­n­i­tions below so that:

   merge­By com­pare xs ys = merge xs ys
   merge­Sort­By com­pare xs == merge­Sort xs
   

Let Color be the red, green, blue or yel­low color data type.

data Color
  = Red | Green | Blue | Yel­low
  deriv­ing (Eq, Show)

The above deriv­ing anno­ta­tion teaches Haskell how to com­pare col­ors and how to turn them to strings for print­ing. Sim­i­larly, the Balkan data type defines the coun­tries that belong in the Balkan area.

data Balkan
  =  Alba­nia | Bul­garia  | Bosnia­And­Herze­gov­ina
  |  Kosovo  | Mace­do­nia | Mon­tene­gro
  deriv­ing (Eq, Show)

Two coun­tries are adja­cent when they share the same bor­der. The below adja­cen­cies list cap­tures all the Balkan adja­cen­cies: x is adja­cent to y when either elem (x,y) adja­cen­cies or elem (y,x) adja­cen­cies.

adja­cen­cies :: [(Balkan,Balkan)]
adja­cen­cies =
   [ (Alba­nia, Mon­tene­gro), (Alba­nia, Kosovo), (Alba­nia, Mace­do­nia)
   , (Bul­garia, Mace­do­nia), (Bosnia­And­Herze­gov­ina, Mon­tene­gro)
   , (Kosovo, Mace­do­nia), (Kosovo, Mon­tene­gro)
   ]

We call col­or­ing a list of type [(Balkan,Color)] that related each Balkan coun­try with a color. A col­or­ing is good with respect to an adja­cency matrix when every two adja­cent coun­tries have a dif­fer­ent color. A col­or­ing is com­plete with respect to an adja­cency matrix when it col­ors every coun­try in the matrix. Good col­or­ings may be incom­plete.

1. Write a func­tion is­Good­Col­or­ing adj col­or­ing that returns True if and only if the col­or­ing list is good with respect to the input adja­cency list.

2. Define col­or­ings to return all the good and com­plete col­or­ings of the adja­cency list adja­cen­cies.

Get together with some of your class­mates to form a final project group. Groups can have at most four peo­ple. Choose a project idea that you want to pur­sue. It doesn’t have to be a par­tic­u­larly orig­i­nal idea, but some­thing that is of sim­i­lar or greater com­plex­ity than our Sudoku pro­gram. Here are some start­ing ideas:

• A pro­gram that can play a game like Con­nect Four, Gomoku, Poker, etc. against a user.

• Any puz­zle solver, other than Sudoku of course.

• A maze gen­er­a­tor and solver.

• An imple­men­ta­tion of a cool data struc­ture, per­haps some­thing from Okasaki’s book Purely Func­tional Data Struc­tures.

• A parser and inter­preter for a small lan­guage, like Dat­a­log or a basic Lisp.

You can really choose any­thing you want, although we may have rec­om­men­da­tions if we think you’ve cho­sen some­thing too easy or dif­fi­cult.