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