Flolac 18 課前作業 (潘冠宇)

flolac18.hs

-- 1. Define a function called myFst which takes a tuple and returns the first component.
myFst :: (a, b) -> a
myFst = fst

-- 2. Define a function myOdd which determines if the input is an odd number or not.
myOdd :: Int -> Bool
myOdd x = x `mod` 2 == 1

-- 3. 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 ]

-- (a) What is Ord? What does the type of qs mean?
-- Ord 是 typeclass, 代表可以比較大小
-- qs 代表傳進一個 list 回傳一個 list 的函數
-- 而且 list 裡面的元素是一樣的 type

-- (b) What is the type of (++)? What does it do?
-- (++) :: [a] -> [a] -> [a] 傳進入兩個 list 回傳一個 list
-- 他是 typclass monoid 的 mappend 運算元，在 list 中代表兩個字串的串接

-- (c) What are the elements of ys and zs, respectively?
-- ys 代表比這個 pivot x 小或等於的元素所組成的 list
-- zs 代表比這個 pivot x 大的元素所組成的 list

-- (d) What does the function qs do?
-- qs 是快速排序法, 主要利用 recusive 與 pivot 來排序 (由小到大)

-- (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' x = case x of
  [] -> []
  (x:xs) -> 
    let 
      ys = [ y | y <- xs, y <= x ]
      zs = [ z | z <- xs, x < z ]
    in qs ys ++ [x] ++ qs zs