Created
July 21, 2022 12:43
-
-
Save chengchingwen/6efe32481cd40e5ae02cb34e1a309d62 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Data.List (sortBy) | |
-- This exercise covers the first 6 and the 8th chapters of "Learn You a Haskell for Great Good!" | |
-- Chapter 1 - http://learnyouahaskell.com/introduction | |
-- Chapter 2 - http://learnyouahaskell.com/starting-out | |
-- Chapter 3 - http://learnyouahaskell.com/types-and-typeclasses | |
-- Chapter 4 - http://learnyouahaskell.com/syntax-in-functions | |
-- Chapter 5 - http://learnyouahaskell.com/recursion | |
-- Chapter 6 - http://learnyouahaskell.com/higher-order-functions | |
-- Chapter 8 - http://learnyouahaskell.com/making-our-own-types-and-typeclasses | |
-- Download this file and then type ":l FLOLAC-22-Tasks.hs" in GHCi to load this exercise | |
-- Some of the definitions are left "undefined", you should replace them with your answers. | |
-- 0. Example: find the penultimate (second-to-last) element in list xs | |
penultimate xs = last (init xs) | |
-- 1. Find the antepenultimate (third-to-last) element in list xs | |
antepenultimate xs = last $ init $ init xs | |
-- 2. Left shift list xs by 1 | |
-- For example, "shiftLeft [1, 2, 3]" should return "[2, 3, 1]" | |
shiftLeft xs = tail xs ++ [head xs] | |
-- 3. Left shift list xs by n | |
-- For example, "rotateLeft 2 [1, 2, 3]" should return "[3, 1, 2]" | |
rotateLeft 0 xs = xs | |
rotateLeft n xs = rotateLeft (n-1) (shiftLeft xs) | |
-- 4. Insert element x in list xs at index k | |
-- For example, "insertElem 100 3 [0,0,0,0,0]" should return [0,0,0,100,0,0] | |
insertElem x k xs = (take k xs) ++ x:(drop k xs) | |
-- Here we have a type for the 7 days of the week | |
-- Try typeclass functions like "show" or "maxBound" on them | |
data Day = Mon | Tue | Wed | Thu | Fri | Sat | Sun | |
deriving (Eq, Ord, Show, Bounded, Enum) | |
-- 5. Note that if you try "succ Sun", you should get an error, because "succ" is not defined on "Sun" | |
-- Define "next", which is like "succ", but returns "Mon" on "next Sun" | |
next :: Day -> Day | |
next Sun = Mon | |
next day = succ day | |
-- 6. Return "True" on weekend | |
isWeekend :: Day -> Bool | |
isWeekend day = day > Fri | |
data Task = Work | Shop | Play deriving (Eq, Show) | |
-- You are given a schedule, which is a list of pairs of Tasks and Days | |
schedule :: [(Task, Day)] | |
schedule = [(Shop, Fri), (Work, Tue), (Play, Mon), (Play, Fri)] | |
-- 7. However, the schedule is a mess | |
-- Sort the schedule by Day, and return only a list of Tasks. | |
-- If there are many Tasks in a Day, you should keep its original ordering | |
-- For example, "sortTask schedule" should return "[(Play, Mon), (Work, Tue), (Shop, Fri), (Play, Fri)]" | |
sortTask :: [(Task, Day)] -> [(Task, Day)] | |
sortTask xs = sortBy (\(_, d1) (_, d2) -> d1 `compare` d2) xs | |
-- 8. This function converts days to names, like "show", but a bit fancier | |
-- For example, "nameOfDay Mon" should return "Monday" | |
nameOfDay :: Day -> String | |
nameOfDay Mon = "Monday" | |
nameOfDay Tue = "Tuesday" | |
nameOfDay Wed = "Wednesday" | |
nameOfDay Thu = "Thursday" | |
nameOfDay Fri = "Friday" | |
nameOfDay Sat = "Saturday" | |
nameOfDay Sun = "Sunday" | |
-- 9. You shouldn't be working on the weekends | |
-- Return "False" if the Task is "Work" and the Day is "Sat" or "Sun" | |
labourCheck :: Task -> Day -> Bool | |
labourCheck Work day = not (isWeekend day) | |
labourCheck _ _ = True | |
-- 10. Raise x to the power y using recursion | |
-- For example, "power 3 4" should return "81" | |
power :: Int -> Int -> Int | |
power _ 0 = 1 | |
power x y = x * (power x (y - 1)) | |
-- 11. Convert a list of booleans (big-endian) to a interger using recursion | |
-- For example, "convertBinaryDigit [True, False, False]" should return 4 | |
convertBinaryDigit :: [Bool] -> Int | |
convertBinaryDigit (x:[]) = fromEnum x | |
convertBinaryDigit bits = fromEnum (last bits) + 2 * (convertBinaryDigit (init bits)) | |
-- 12. Create a fibbonaci sequence of length N in reverse order | |
-- For example, "fib 5" should return "[3, 2, 1, 1, 0]" | |
fib :: Int -> [Int] | |
fib 1 = [0] | |
fib 2 = [1, 0] | |
fib n = (sum (take 2 previous)):(previous) where previous = fib (n - 1) | |
-- 13. Determine whether a given list is a palindrome | |
-- For example, "palindrome []" or "palindrome [1, 3, 1]" should return "True" | |
palindrome :: Eq a => [a] -> Bool | |
palindrome (x:[]) = True | |
palindrome (x:y:[]) = x == y | |
palindrome xs = (head xs) == (last xs) && (palindrome (init (tail xs))) | |
-- 14. Map the first component of a pair with the given function | |
-- For example, "mapFirst (+3) (4, True)" should return "(7, True)" | |
mapFirst :: (a -> b) -> (a, c) -> (b, c) | |
mapFirst f pair = (f (fst pair), snd pair) | |
-- 15. Devise a function that has the following type | |
someFunction :: (a -> b -> c) -> (a -> b) -> a -> c | |
someFunction r f x = r x (f x) | |
-- Here is an algebraic datatype representing trees. | |
-- Be careful, these trees are somehow different from those defined in the book! | |
-- Apparently our trees are better, they have leaves, and data is stored on leaves. | |
data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show) | |
-- 16. What is the map function as well as the Functor instance for this tree? | |
-- (You may want to lookup the Functor typeclass.) | |
instance Functor Tree where | |
fmap f (Leaf a) = Leaf (f a) | |
fmap f (Node a b) = Node (fmap f a) (fmap f b) | |
-- We say a tree is flattenable if it can be turned into a list | |
-- which contains all elements originally in the tree. | |
data List a = Nil | Cons a (List a) deriving Show | |
-- We can define a typeclass to express that. | |
class Flattenable t where | |
flatten :: t a -> List a | |
-- 17. Show that our Tree is flattenable: | |
instance Flattenable Tree where | |
flatten (Leaf a) = Cons a Nil | |
flatten (Node (Leaf a) b) = Cons a (flatten b) | |
flatten (Node (Node a b) c) = flatten (Node a (Node b c)) | |
-- 18. Define a type of trees that have leaves and two kinds of nodes: | |
-- one with two branches and another with three branches. | |
-- Your tree should have three constructors. | |
-- You can choose where to store data (either on leaves, nodes, or both). | |
-- | |
data TwoThreeTree a = TLeaf a | | |
TNode2 (TwoThreeTree a) (TwoThreeTree a) | | |
TNode3 (TwoThreeTree a) (TwoThreeTree a) (TwoThreeTree a) | |
deriving (Show) | |
-- 19. Show that the datatype you just defined is flattenable: | |
-- | |
instance Flattenable TwoThreeTree where | |
flatten (TLeaf a) = Cons a Nil | |
flatten (TNode3 a b c) = flatten (TNode2 a (TNode2 b c)) | |
flatten (TNode2 (TLeaf a) b) = Cons a (flatten b) | |
flatten (TNode2 (TNode2 a b) c) = flatten (TNode2 a (TNode2 b c)) | |
flatten (TNode2 (TNode3 a b c) d) = flatten (TNode2 a (TNode3 b c d)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment