alan23273850

6/1/2018 - 3:52 PM

```
-- Problem 1)
myFst :: (a, b) -> a
myFst (a, b) = a -- Method 1 (man-made function)
--myFst = fst -- Method 2 (built-in function)
-- Problem 2)
myOdd :: Int -> Bool
myOdd(x) = (x `mod` 2) == 1 -- Method 1 (man-made function)
--myOdd x = odd x -- Method 2 (built-in function)
-- Problem 3)
-- a) "Ord a" means that all elements of type 'a' must be comparable to each other.
-- The type of 'qs' means that the function accepts something which is a list of
-- type 'a' as its argument, and return something which is also a list of type 'a'
-- as its result.
-- b) The answer can be obtained with the command ":t (++)" so the type of (++) is
-- (++) :: [a] -> [a] -> [a]. It is a binary operator. It just concatenates two
-- lists with time complexity depending on the length of the list on the left of ++.
-- c) 'ys' is a list that contains all elements not larger than x (the first element of
-- qs) and preserves the order of elements.
-- 'zs' is a list that contains all elements larger than x (the first element of qs)
-- and preserves the order of elements.
-- d) The function 'qs' simply performs the famous sorting algorithm, quicksort.
-- It first selects its first element 'x' as the pivot, then collects all elements
-- not larger than 'x' into a sublist 'ys', then collects all elements larger than 'x'
-- into a sublist 'zs', and then finally put 'ys' and 'zs' on the left and right of
-- 'x' respectively. One 'qs' function just does one iteration of the quicksort algo.
-- e) The rewritten function is as follows.
qs' :: Ord a => [a] -> [a]
qs' [] = []
qs' xs =
let x = head xs
w = drop 1 xs
in qs' [ y | y <- w, y <= x ] ++ [x] ++ qs' [ z | z <- w, z > x ]
-- Here I want to transform [y|y<-w,y<=x] and [z|z<-w,z>x] into another function using case
-- operator, but it seems a little bit difficult. :((
-- Hope there is some beautiful solution I can learn from !
```