Homework 3
Due on Oct 19 Wednesday

1. Define the following library functions using recursion:

  1. Produce a list with n identical elements: 

    replicate :: Int -> a -> [a]
replicate n x = undefined

  2. Select the nth element of a list: 

    (!!) :: [a] -> Int -> a
xs !! i = undefined

  3. Decide if a value is an element of a list: 

    elem :: Eq a => a -> [a] -> Bool

2. Merge and Sort

  1. Define a recursive function 
    merge :: Ord a => [a] -> [a] -> [a]
    that merges two sorted lists of values to give a single sorted list. For example: 
    Prelude λ> merge [2,5,6] [1,3,4]
[1,2,3,4,5,6]
  2. Define a recursive function 
    msort :: Ord a => [a] -> [a]
    that implements merge sort, which can be specified by the following two rules:
    • Lists of length 1 are already sorted;
    • Other lists can be sorted by sorting the two halves and merging the resulting lists.

3. Higher-order functions

  1. Express the comprehension 

    [f x | x  xs, p x]

    using the functions map and filter.

  2. Redefine map f and filter p using foldr. (Hint: What is the type of map f? And how about the type of filter p?)

4. Number representations and Arithmetics

  1. Convert (8729)12 into its octet (base-8) representation.

  2. Write a haskell function that converts any base-8 (octet) number into its base-6 (senary) form. 

    octet2senary :: [Int] -> [Int]
octet2senary xs = undefined

    For example, to obtain the senary representation of (345)8, you can call 

    Prelude λ> octet2senary [3,4,5]    
[1,0,2,1]

    to get (1021)6.

  3. Write a Haskell function that adds two base-8 numbers represented as lists. For example, to add (6273)8 and (7712)8 in ghci, you type 

    Prelude λ> addoctets [6,2,7,3] [7,7,1,2]    
[1,6,2,0,5]

    You can use the following code stub to get yourself started. 

    addoctets :: [Int] -> [Int] ->[Int]
addoctets = undefined

5. Bonus Problems