The first part of the following questions requires basic understanding of how to define a function in Haskell. The second part is a recursive function using techniques you should have learned from the first 4 chapters of Learn You a Haskell for Great Good!. Please check your answer using the interactive interpreter ghci before submission. If you are not familiar with the command-line interface, please read the first chapter of Real World Haskell.
- Define a function called myFst which takes a tuple and returns the first component.
myFst :: (a, b) -> a
myFst (a, b) = a- Define a function myOdd which determines if the input is an odd number or not. Hint: You may use mod (what is this?).
myOdd :: Int -> Bool
myOdd n = n `mod` 2 /= 0- Consider the following function.
qs :: Ord a => [a] -> [a]
qs [] = []
qs (x:xs) = qs ys ++ [x] ++ qs zs
where
ys = [ y | y <- xs, y <= x ]
zs = [ z | z <- xs, x < z ]Please answer the following questions concisely either in plain English or Chinese.
(a) What is Ord? What does the type of qs mean?
Ord 是一個 typeclass, 代表型別 a 必須是屬於 Ord 這個 typeclass 的型別，Ord 也代表著是一個可以排序的型別的集合。 而 qs 是一個函式，將接收一個內容可以排序的串列並且回傳一個內容同樣型別的串列。
(b) What is the type of (++)? What does it do?
(++) 的型別是一個函式，它將接收兩個 type 為 a 的串列，並且產出一個 type 為 a 的串列，而功能上是將兩個串列串連起來。
(c) What are the elements of ys and zs, respectively?
ys 的元素是從 xs 中的元素取出小於等於 x 的子集 zs 的元素是從 xs 中元素取出大於 x 的子集
(d) What does the function qs do? Hint: If you are not familiar with recursive functions (functions which are defined in terms of themselves), run qs on some lists (e.g., [2, 1, 4, 3, 5]) and make a guess.
quick sort, 將第一個元素當作 pivot x，剩餘元素中小於等於 x 放到 x 左邊的 list，大於 x 的放到右邊的 list，再分別對左右的 list 進行 quick sort。直到要排序的 list 內沒有元素了終止。
(e) Please re-write the function qs above and call it qs’ using let expression and case expression instead of where clause and pattern matching.
qs' :: Ord a => [a] -> [a]
qs' [] = []
qs' (x:xs) = let ys = [ y | y <- xs, y <= x ]
in let zs = [ z | z <- xs, x < z ]
in qs' ys ++ [x] ++ qs' zs