Haskell Programming (Not any other Language): Simply answer the question (Code)
8. [8 points] The next data structure is for encoding patterns that describe lists of values. data Pattern a -P a | POr (Pattern a) (Pattern a) | PAnd (Pattern a) (Pattern a) deriving Show Your task will be to complete a partially-written match routine that tries to match a pattern with a list of values. match pat vals (False, vals) means that the match failed, and the vals are being returned as is. match pat vals- (True vals2) means that the pattern matched the head of vals and removed that head with vals2 leftover. match (P 1) [1, 2, 3] -(True, [2, 3]) match (P 1) [2, 3, 4] - (False, [2, 3, 4]) match (P1) -(False, 1) You can't match the empty list The POr constructor takes two pattern and returns a pattern that tries to match one or the other. E.g. match ((P 1) POr (P 2)) [1, 2, 3]-(True, [2, 31) match ((P 1) POr(P 2)) [2, 1, 3] - (True, [1, 31) match ((P 1) POr (P 2)) [7] - (False, [7]) The leftover list comes from whichever match was successful The PAnd constructor concatenates two patterns. E.g. match ((P 1) PAnd (P 2)) [1, 2, 3]- (True, [3]) because [3] was leftover after matching 1 and then 2. If the first pattern fails to match, we don't try the second pattern: match ((P 1) PAnd (P 2)) [4, 5]- (False [4, 5] The only subtle part is that if the first pattern matches but the second one doesn't, we don't return the list from the failed second pattern match, we return the original list. match ((P 1) PAnd (P 2)) [1, 4, 5]- (False, [1, 4, 5]) Here, match (P 1) [l, 4, 5] returned (True, [4, 5]) but match (P 2) [4, 5 ] returned (False, [4, 5]). Nonetheless, the PAnd returned what it started with, namely [1, 4, 5] Here is the code for matching the empty list, P, and POr. Your job is to add the code for the PAnd case match _ [ ] = (False, [ ] ) match (P x) (y : ys) - if x --y then (True, ys) else (False, y : ys) match (POr patl1 pat2) xs - case match patl xs of (True, leftover) -> (True, leftover) -- stop if patl succeeded (False, _) -> match pat2 xs -- else try pat2 (You add PAnd) 8. [8 points] The next data structure is for encoding patterns that describe lists of values. data Pattern a -P a | POr (Pattern a) (Pattern a) | PAnd (Pattern a) (Pattern a) deriving Show Your task will be to complete a partially-written match routine that tries to match a pattern with a list of values. match pat vals (False, vals) means that the match failed, and the vals are being returned as is. match pat vals- (True vals2) means that the pattern matched the head of vals and removed that head with vals2 leftover. match (P 1) [1, 2, 3] -(True, [2, 3]) match (P 1) [2, 3, 4] - (False, [2, 3, 4]) match (P1) -(False, 1) You can't match the empty list The POr constructor takes two pattern and returns a pattern that tries to match one or the other. E.g. match ((P 1) POr (P 2)) [1, 2, 3]-(True, [2, 31) match ((P 1) POr(P 2)) [2, 1, 3] - (True, [1, 31) match ((P 1) POr (P 2)) [7] - (False, [7]) The leftover list comes from whichever match was successful The PAnd constructor concatenates two patterns. E.g. match ((P 1) PAnd (P 2)) [1, 2, 3]- (True, [3]) because [3] was leftover after matching 1 and then 2. If the first pattern fails to match, we don't try the second pattern: match ((P 1) PAnd (P 2)) [4, 5]- (False [4, 5] The only subtle part is that if the first pattern matches but the second one doesn't, we don't return the list from the failed second pattern match, we return the original list. match ((P 1) PAnd (P 2)) [1, 4, 5]- (False, [1, 4, 5]) Here, match (P 1) [l, 4, 5] returned (True, [4, 5]) but match (P 2) [4, 5 ] returned (False, [4, 5]). Nonetheless, the PAnd returned what it started with, namely [1, 4, 5] Here is the code for matching the empty list, P, and POr. Your job is to add the code for the PAnd case match _ [ ] = (False, [ ] ) match (P x) (y : ys) - if x --y then (True, ys) else (False, y : ys) match (POr patl1 pat2) xs - case match patl xs of (True, leftover) -> (True, leftover) -- stop if patl succeeded (False, _) -> match pat2 xs -- else try pat2 (You add PAnd)
