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

Merge Sort

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)
  (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.

Final Project

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:

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.