Title : Homework 3
Title Note : Due on Oct 19 Wednesday
Author :
Email :
Doc class : [11pt]article
~ MathDefs
\newcommand{\jacobi}[2]{\ensuremath{\left(\frac{#1}{#2}\right)}}
~
[TITLE]
# Define the following library functions using recursion:
a. Produce a list with n identical elements:
``` haskell
replicate :: Int -> a -> [a]
replicate n x = undefined
```
- Select the nth element of a list:
``` haskell
(!!) :: [a] -> Int -> a
xs !! i = undefined
```
- Decide if a value is an element of a list:
``` haskell
elem :: Eq a => a -> [a] -> Bool
```
# Merge and Sort
a. Define a recursive function
``` haskell
merge :: Ord a => [a] -> [a] -> [a]
```
that merges two sorted lists of values to give a single sorted list. For example:
``` {padding-left:1ex; padding-right:1ex; padding-top:.75ex; padding-bottom:.25ex; background-color:black; color:white; font-size:14pt }
Prelude λ> merge [2,5,6] [1,3,4]
[1,2,3,4,5,6]
```
b. Define a recursive function
``` haskell
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.
\
# Higher-order functions
a. Express the comprehension
``` haskell
[f x | x xs, p x]
```
using the functions `map` and `filter`.
* Redefine `map f` and `filter p` using `foldr`. (Hint: What is the type of `map f`? And how about the type of `filter p`?)
# Number representations and Arithmetics
a. Convert (8729)~12~ into its octet (base-8) representation.
* Write a haskell function that converts any base-8 (_octet_) number into its base-6 (_senary_) form.
``` haskell
octet2senary :: [Int] -> [Int]
octet2senary xs = undefined
```
For example, to obtain the senary representation of (345)~8~, you can call
``` {padding-left:1ex; padding-right:1ex; padding-top:.75ex; padding-bottom:.25ex; background-color:black; color:white; font-size:14pt }
Prelude λ> octet2senary [3,4,5]
[1,0,2,1]
```
to get (1021)~6~.
* 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
``` {padding-left:1ex; padding-right:1ex; padding-top:.75ex; padding-bottom:.25ex; background-color:black; color:white; font-size:14pt }
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.
``` haskell
addoctets :: [Int] -> [Int] ->[Int]
addoctets = undefined
```
# Bonus Problems
* **[10 points]** Write a Haskell function that multiplies two base-`b` numbers.
``` haskell
mult :: Int -> [Int] -> [Int] ->[Int]
mult = undefined
```
* **[10 points]** Write a Haskell function that divides two base-`b` numbers.
``` haskell
divmod :: Int -> [Int] -> [Int] ->[Int]
divmod = undefined
```