Homework 1

Instructions

The source code of this homework can be found here. You should fill in the definitions of the required functions but do not change the types of the functions.

How to submit: TBA

> module HW1 where
> import Data.Char 

Problem 1: Strings

In Haskell the String data type is defined to be a list of Characters, so String can be manipulated via list comprehension.

For example, bellow 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"]

You are requested to use list comprehension to define the following two functions on Strings.

1. Complete the function removeUpper that removes all uppercase characters from its String argument. For example removeUpper "Hello World!" = "ello orld!". Hint: use the library function isLower.

> removeUpper :: String -> String
> removeUpper xs = error "Define me!"

2. 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. For example noIdent "Hello World!" = "HelloWorld". Hint: use the library function elem.

> noIdent :: String -> String
> noIdent xs = error "Define me!"

3. Now use recursion to define the function isPrefixOf xs ys that turns True if and only if xs is prefix of ys. For example isPrefixOf "Haskell" "I like Haskell" = False and isPrefixOf "I like" "I like Haskell" = True.

> isPrefixOf :: String -> String -> Bool 
> isPrefixOf xs ys = error "Define me!"

Problem 2: Factoring

We say that a is a factor of n when there exists an integer b so that n = a * b.

1. Define a function factors n that returns all functors of n. For example, factors 12 = [1,2,3,4,6,12] and factors 13 = [1,13].

> factors :: Int -> [Int] 
> factors n = error "Define me!"

We say that an integer n is prime when its only factors are 1 and n.

2. Define a function isPrime n that returns True if and only if n is prime. For example isPrime 12 = False and isPrime 13 = True.

> isPrime :: Int -> Bool 
> isPrime n = error "Define me!"

3. Optimize the factors n function to only call the mod function at most √ n  times. Note that factors appear in pairs. If you found i to be a factor of n, then div n i is also a factor of n. Hint: define a helper recursive function factorsRec n i and recurse on increasing i.

> factorsOpt :: Int -> [Int]
> factorsOpt n = error "Define me!"

4. Test your optimization. The below function sameElems xs ys checks that the two input lists have the same elements, by checking that

   • the two input lists have same length and
   • all elements of the list xs are elements of the list ys.

> sameElems :: [Int] -> [Int] -> Bool 
> sameElems xs ys =  length xs == length ys 
>                 && all (`elem` ys) xs

Use sameElems to write a function testFactors n that tests that the two factor functions you wrote above return the same factors for every integer up to n. Hint: use the library function and.

> testFactors :: Int -> Bool 
> testFactors n = error "Define me!"

Problem 3: Coloring

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

Note the above deriving annotation teaches Haskell how to compare colors and how to turn them to strings for printing.

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

1. 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.

> isGoodColoring :: [(Balkan, Balkan)] -> [(Balkan,Color)] -> Bool 
> isGoodColoring adj coloring = error "Define me!"

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

> colorings :: [[(Balkan, Color)]]
> colorings = error "Define me!"