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

• [10 points] Write a Haskell function that multiplies two base-b numbers.
mult :: Int -> [Int] -> [Int] ->[Int]
mult = undefined
• [10 points] Write a Haskell function that divides two base-b numbers.
divmod :: Int -> [Int] -> [Int] ->[Int]
divmod = undefined