Haskell Programming: Simply answer the question (Code)

HW04_part1.hs (Let me know if text file need instead of picture of this file)

For this assignment, you'll be modifying and extending our earlier implementation of matching regular expressions against strings. In addition to the expressions we already have: (empty string a specified character, alternation, and concatenation, we'll add $ for end of string: a match of S with the empty string succeeds and matches the empty string; a match of S against any non-empty string fails .. for any single character: dot matches any one character in the alphabet . ? for optional expression: exp ? is like (exp l e): The expression or empty string (note it always succeeds. . Kleene star: exp* is like (exp exp*) e. However, if exp matches but returns the empty string as the match, then just succeed with that. This is to avoid infinite recursion on expressions like e*. In addition, there's a change to how exp1 exp2 should behave: If both sides succeed, we want the result with the longer matching string. E.g., a match of ("a" | "ab" "abc" should succeed with "ab" (and leftover "c"). The way we were doing it before (skip exp2 if expl succeeds) can fail to return the longest match, which is now our goal. Part 1. Backtracking Search This is a extension and modification to the earlier backtracking search program. There are two data structures data RegExp (the regular expressions) data Mresult FAIL | oK String String deriving (Eq, Show) An unsuccessful match should return FAIL. A successful result OK strl str2 means that str1 matched the expression and str2 was leftover. Note strl ++ str2 should equal the string passed to match. E g., matching (Rch ) against "abc" should yield OK "a" "bc" There's a skeleton program HW04_partl.hs it compiles but its match always returns FAIL. You should replace the stub code with your implementation Homework 4 part 1 -Match regular expressions using backtracing search - Simple Regular Expressions with expl. exp2, expp2, null string (epsilon), $(end of string), dot (any single character), optional expr. (? exp), and Kleene star data RegExRRnul -- e empty string epsilon -- $ at end of string? -- . any one character --a specific character -- | alternation Rend Rch Char Ror RegExp RegExp. Rand RegExp RegExp Ropt RegEXP -- concatenation -- ? optional expression - *Kleene star I Rstar RegExp. deriving (Eq, Show) -- A match result oK strl str2 means that stri matched the expression and -- str2 was leftover. Note stri ++ str2 should be the string passed to match. data Mresu], FAIL ! 0K String String deriving (Eq, Show) Matching takes a regular expression and a string and either fails or -- returns the string that matched and the string that was leftover. match :: BegExp"-> String-> Mresu, You fill in STUBS below -Matching empty string always succeeds, with empty string as the matched string match Rnull str = FAIL-STUB -Match Rend str succeeds iff we're at the end of the string (str is null) match Rend str = FAIL -- STUB -Match Rany, string matches the first character of the string (failing if string 15 null) match Bany, str = FAIL-STUB Match a character succeeds iff the string begins with the character match (Rshch1} str= FAIL -- STUB - Match Ror. rl r2) string matches rl against string and also r2 against string -- and fails if both fail, returns the successful result if exactly one succeeds, -- and returns the result with the longer match if both succeed match (Br. resRA resp2) str = FAIL -- STUB Match (Rand rl r2) string matches rl and (if it succeeds) matches r2 against -- the string leftover from rl. If r2 succeeds then the Rand returns the -- concatenation of the matches from r1 and r2. match (Rand rese! rexR2) str= FAIL-STUB Matching an optional expression is like matching (rexp. null) match (Bont, rexp) str= FAIL-STUB matching rexp* is like matching ((rexp. rexpnull), but to avoid infinit String-> Mresu, You fill in STUBS below -Matching empty string always succeeds, with empty string as the matched string match Rnull str = FAIL-STUB -Match Rend str succeeds iff we're at the end of the string (str is null) match Rend str = FAIL -- STUB -Match Rany, string matches the first character of the string (failing if string 15 null) match Bany, str = FAIL-STUB Match a character succeeds iff the string begins with the character match (Rshch1} str= FAIL -- STUB - Match Ror. rl r2) string matches rl against string and also r2 against string -- and fails if both fail, returns the successful result if exactly one succeeds, -- and returns the result with the longer match if both succeed match (Br. resRA resp2) str = FAIL -- STUB Match (Rand rl r2) string matches rl and (if it succeeds) matches r2 against -- the string leftover from rl. If r2 succeeds then the Rand returns the -- concatenation of the matches from r1 and r2. match (Rand rese! rexR2) str= FAIL-STUB Matching an optional expression is like matching (rexp. null) match (Bont, rexp) str= FAIL-STUB matching rexp* is like matching ((rexp. rexpnull), but to avoid infinit