2018 年報名 flolac 所要求的課前測驗

flolac-prerequisites.hs

-- 作者 gholk
-- 日期 2018-05-31

{- 2018 年報名 flolac 所要求的課前測驗，
昨天看完前三章，現在邊看第四章邊把測驗寫完了。 -}


-- 1
myFst :: (a,b) -> a
myFst (a,b) = a


-- 2
myOdd :: Integral n => n -> Bool
myOdd n = mod n 2 == 0


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

-- 3
-- 3 - a
{- Ord 是指可被排序的資料，
實作上指支援 compare 函數的資料，
也就是可以用 `><=` 比較大小與相等與否。 -}

{- qs 的類型是 `Ord a => [a] -> [a]` ，
也就是該函數接受一個由可排序的類型組成的列表 (list) ，
然後返回一個同樣類型組成的列表。 -}

-- 3 - b
-- (++) :: [a] -> [a] -> [a]

{- `++` 是一個中綴函數，
接受左右二個列表，返回一個同類型的列表。 -}

{- 實際上 `++` 做的事和 lisp 中的 append 差不多，
接受二個列表，然後複製二者並串接成另一個新的列表返回。 -}

-- 3 - c
{- `ys` 是 `xs` 的元素中，所有小於等於 `x` 的元素組成的列表；
`zs` 是 `xs` 中所有大於 `x` 的元素組成的列表；
並 `x` 是函數 qs 參數的表中的第一個元素。-}

-- 3 - d
{- qs 函數接受一個列表，用快速排序法排序後返回。 -}

-- 1. 先將列表分為第一個元素 x，和其餘元素組成的列表 xs。
-- 2. 隨後取出所有 xs 中小於等於 x 的元素，組成 ys 列表，
-- 3. 取出 xs 中大於 x 的元素，組成 zs 列表。
-- 4. 分別將 ys 與 zs 用 qs 排序，
-- 5. 將排序後的 ys x zs 串接成新的列表並返回。
 
{- 在其中，qs 會被遞迴呼叫。
如果 qs 的參數表只有一個元素，
則 xs 成為空表，ys zs 也隨之成為空表。
空表串接也只是空表，且 qs 若參數是空表，
也會直接返回，作為 qs 遞迴的終止條件。 -}

-- 3 - e
qs' list = case list of
    [] -> []
    nonEmpty -> let pivot = head nonEmpty
                    other = tail nonEmpty
                    greater = [ g | g <- other, g > pivot ]
                    less = [ l | l <- other, l <= pivot ]
        in qs' less ++ [pivot] ++ qs' greater