This is your task, I have provided both the instructions and the scaffold, implement it. before creating the parsers, create a BNF for markdown, Then u will know how each parser is meant to look like. Here is information on parser combinators:

Parser Combinators
43 min read

Learning Outcomes
Understand that a parser is a program which extracts information from structured text
Apply what we have learned about Haskell typeclasses and other functional programming concepts to create solutions to real-world problems
In particular, we learn to use parser combinators and see how they are put together
Introduction
In this section we will see how the various Haskell language features we have explored allow us to solve real-world problems. In particular, we will develop a simple but powerful library for building parsers that is compositional through Functor, Applicative and Monad interfaces. Before this, though, we will learn the basics of parsing text, including a high-level understanding that parsers are state-machines which realise a context-free grammar over a textual language.

Previously, we glimpsed a very simplistic Applicative parser. In this chapter, a parser is still simply a function which takes a string as input and produces some structure or computation as output, but now we extend the parser with monadic “bind” definitions, richer error handling and the ability to handle non-trivial grammars with alternative inputs.

Parsing has a long history and parser combinators are a relatively recent approach made popular by modern functional programming techniques.
A parser combinator is a higher-order function that accepts parsers as input and combines them somehow into a new parser.

More traditional approaches to parsing typically involve special purpose programs called parser generators, which take as input a grammar defined in a special language (usually some derivation of BNF as described below) and generate the partial program in the desired programming language which must then be completed by the programmer to parse such input. Parser combinators have the advantage that they are entirely written in the one language. Parser combinators written in Haskell take advantage of the expressiveness of the Haskell language such that the finished parser can look a lot like a BNF grammar definition, as we shall see.

The parser combinator discussed here is based on one developed by Tony Morris and Mark Hibberd as part of their “System F” Functional Programming Course, which in turn is a simplified version of official Haskell parser combinators such as parsec by Daan Leijen.

You can play with the example and the various parser bits and pieces in this on-line playground.

Context-free Grammars and BNF
Fundamental to analysis of human natural language but also to the design of programming languages is the idea of a grammar, or a set of rules for how elements of the language may be composed. A context-free grammar (CFG) is one in which the set of rules for what is produced for a given input (production rules) completely cover the set of possible input symbols (i.e. there is no additional context required to parse the input). Backus-Naur Form (or BNF) is a notation that has become standard for writing CFGs since the 1960s. We will use BNF notation from now on. There are two types of symbols in a CFG: terminal and non-terminal. In BNF non-terminal symbols are <nameInsideAngleBrackets> and can be converted into a mixture of terminals and/or nonterminals by production rules:

<nonterminal> ::= a mixture of terminals and <nonterminal>s, alternatives separated by |
Thus, terminals may only appear on the right-hand side of a production rule, non-terminals on either side. In BNF each non-terminal symbol appears on the left-hand side of exactly one production rule, and there may be several possible alternatives for each non-terminal specified on the right-hand side. These are separated by a | (in this regard they look a bit like the syntax for algebraic data type definitions).

Note that production rules of the form above are for context-free grammars. As a definition by counter-example, context sensitive grammars allow terminals and more than one non-terminal on the left hand side.

Here’s an example BNF grammar for parsing Australian land-line phone numbers, which may optionally include a two-digit area code in brackets, and then two groups of four digits, with an arbitrary number of spaces separating each of these, e.g.:

(03) 9583 1762
9583 1762

Here’s the BNF grammar:

<phoneNumber> ::= <fullNumber> | <basicNumber>
<fullNumber> ::= <areaCode> <basicNumber>
<basicNumber> ::= <spaces> <fourDigits> <spaces> <fourDigits>
<fourDigits> ::= <digit> <digit> <digit> <digit>
<areaCode> ::= "(" <digit> <digit> ")"
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<spaces> ::= " " <spaces> | ""
So "0"-"9", "(", ")", and " " are the full set of terminals.

Now here’s a sneak peak at a simple parser for such phone numbers. It succeeds for any input string which satisfies the above grammar, returning a 10-digit string for the full number without spaces and assumes “03” for the area code for numbers with none specified (i.e. it assumes they are local to Victoria). Our Parser type provides a function parse which we call like so:

GHCi> parse phoneNumber "(02)9583 1762"
Result >< "0295831762"

GHCi> parse phoneNumber "9583  1762"
Result >< "0395831762"

GHCi> parse phoneNumber "9583-1762"
Unexpected character: "-"
We haven’t bothered to show the types for each of the functions in the code below, as they are all ::Parser [Char] - meaning a Parser that returns a string. We’ll explain all the types and functions used in due course. For now, just notice how similar the code is to the BNF grammar definition:

phoneNumber = fullNumber <|> (("03"++) <$> basicNumber)

fullNumber = do
   ac <- areaCode
   n <- basicNumber
   pure (ac ++ n)

basicNumber = do
   spaces
   first <- fourDigits
   spaces
   second <- fourDigits
   pure (first ++ second)

fourDigits = do
  a <- digit
  b <- digit
  c <- digit
  d <- digit
  pure [a,b,c,d]

areaCode = do
  is '('
  a <- digit
  b <- digit
  is ')'
  pure [a,b]
Parser Type
In essence, our parser is going to be summed up by a couple of types:

type Input = String
newtype Parser a = P { parse :: Input -> ParseResult a}
We assume all Input is a String, i.e. Haskell’s basic builtin String which is a list of Char.

Then the Parser type has one field parse which is a function of type Input -> ParseResult a. So it parses strings and produces parse results, where a Parse result is:

 data ParseResult a = Error ParseError
                    | Result Input a
  deriving Eq
We’ll come back to the ParseError type - which will be returned in the case of unexpected input, but we can see that a successful Parse is going to produce a Result which has two fields—more Input (the part of the input remaining after we took a bit off and parsed it), and an a, a type parameter that we may specify for concrete Parser instances.

The Parser and the ParseResult types are pretty abstract. They say nothing about what precise Input string we are going to parse, or what type a we are going to return in the result. This is the strength of the parser, allowing us to build up sophisticated parsers for different input grammars through composition using instances of Functor, Applicative and Monad, and the ParseResult parameter a allows us to produce whatever we want from the parsers we create.

Error Handling
Error handling is a very important part of any real-world parser. Decent error reporting allows us to quickly diagnose problems in our input. As we saw above a ParseResult may be either a successful Result or an Error, the latter containing information in a ParseError data structure about the nature of the error.

data ParseError =
    UnexpectedEof -- hit end of file when we expected more input
  | ExpectedEof Input -- should have successfully parsed everything but there’s more!
  | UnexpectedChar Char
  | UnexpectedString String
  deriving (Eq, Show)
Naturally it needs to be Showable, and we’ll throw in an Eq for good measure.

Instances
First an instance of Show to pretty print the ParseResults:

instance Show a => Show (ParseResult a) where
  show (Result i a)                 = "Result >" ++ i ++ "< " ++ show a
  show (Error UnexpectedEof)        = "Unexpected end of stream"
  show (Error (UnexpectedChar c))   = "Unexpected character: " ++ show [c]
  show (Error (UnexpectedString s)) = "Unexpected string: " ++ show s
  show (Error (ExpectedEof i))      =
    "Expected end of stream, but got >" ++ show i ++ "<"
And ParseResult is also an instance of Functor so that we can map functions over the output of a successful parse—or do nothing if the result is an Error:

instance Functor ParseResult where
  fmap f (Result i a) = Result i (f a)
  fmap _ (Error e)    = Error e
A Parser itself is also a Functor. This allows us to create a new Parser by composing functionality onto the parse function for a given Parser:

instance Functor Parser where
  fmap :: (a -> b) -> Parser a -> Parser b
  fmap f (P p) = P (fmap f . p)
The applicative pure creates a Parser that always succeeds with the given input, and thus forms a basis for composition. We saw it being used in the above example to return the results of a parse back into the Parser at the end of a do block.

The (<*>) allows us to map functions in the Parser over another Parser. As with other Applicative instances, a common use case would be composition with a Parser that returns a data constructor as we will see in the next example.

instance Applicative Parser where
  pure :: a -> Parser a
  pure x = P (`Result` x)

  (<*>) :: Parser (a -> b) -> Parser a -> Parser b
  (<*>) p q = p >>= (<$> q)
The Monad instance’s bind function (>>=) we have already seen in use in the example above, allowing us to sequence Parsers in do-blocks to build up the implementation of the BNF grammar.

instance Monad Parser where
  (>>=) :: Parser a -> (a -> Parser b) -> Parser b
  (>>=) (P p) f = P (
    \i -> case p i of
      Result rest x -> parse (f x) rest
      Error e -> Error e)
Parser Combinators
The most atomic function for a parser of String is to pull a single character off the input. The only thing that could go wrong is to find our input is empty.

character :: Parser Char
character = P parseit
  where parseit "" = Error UnexpectedEof
        parseit (c:s) = Result s c
The following is how we will report an error when we encounter a character we didn’t expect. This is not the logic for recognising a character, that’s already happened and failed and the unrecognised character is now the parameter. This is just error reporting, and since we have to do it from within the context of a Parser, we create one using the P constructor. Then we set up the one field common to any Parser, a function which returns a ParseResult no matter the input, hence const. The rest creates the right type of Error for the given Char.

unexpectedCharParser :: Char -> Parser a
unexpectedCharParser = P . const . Error . UnexpectedChar
Now a parser that insists on a certain character being the next one on the input. It’s using the Parser instance of Monad’s bind function (implicitly in a do block) to sequence first the character Parser, then either return the correct character in the Parser, or the Error parser.

is :: Char -> Parser Char
is c = do
  v <- character
  let next = if v == c
             then pure
             else const $ unexpectedCharParser v
  next c
And finally we introduce the Alternative typeclass for our Parser for trying to apply a first Parser, and then an alternate Parser if the first fails. This allows us to encode the alternatives in our BNF grammar rules.

instance Alternative Parser where
  empty :: Parser a
  empty = Parser $ const (Error UnexpectedEof)

  p1 <|> p2 = P (\i -> let f (Error _) = parse p2 i
                         f r = r
                     in f $ parse p1 i)
Nitty gritty
The last two pieces of our Phone Numbers grammar we also implement fairly straightforwardly from the BNF. In a real parser combinator library you’d do it differently, as per our exercises below.

<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<spaces> ::= " " <spaces> | ""
Here’s a trivial adaptation of digit:

digit :: Parser Char
digit = is '0' <|> is '1' <|> is '2' <|> is '3' <|> is '4' <|> is '5' <|> is '6' <|> is '7' <|> is '8' <|> is '9'
Spaces is a bit more interesting because it’s recursive, but still almost identical to the BNF:

spaces :: Parser ()
spaces = (is ' ' >> spaces) <|> pure ()
Exercises
make a less repetitive digit parser by creating a function satisfy :: (Char -> Bool) -> Parser Char which returns a parser that produces a character but fails if the input is empty or the character does not satisfy the given predicate. You can use the isDigit function from Data.Char as the predicate.

change the type of spaces to Parser [Char] and have it return the appropriately sized string of only spaces.

A Parser that returns an ADT
The return type of the phone number parser above was [Char] (equivalent to String). A more typical use case for a parser though is to generate some data structure that we can then process in other ways. In Haskell, this usually means a parser which returns an Algebraic Data Type (ADT). Here is a very simple example.

Let’s imagine we need to parse records from a vets office. It treats only three types of animals. As always, lets start with the BNF:

<Animal> ::= "cat" | "dog" | "camel"
So our simple grammar consists of three terminals, each of which is a straightforward string token (a constant string that makes up a primitive word in our language). To parse such a token, we’ll need a parser which succeeds if it finds the specified string next in its input. We’ll use our is parser from above (which simply confirms a given character is next in its input). The type of is was Char -> Parser Char. Since Parser is an instance of Applicative, we can simply traverse the is parser across the given String (list of Char) to produce another String in the Parser applicative context.

string :: String -> Parser String
string = traverse is
Now let’s define an ADT for animals:

data Animal = Cat | Dog | Camel
  deriving Show
A parser for “cat” is rather simple. If we find the string "cat" we produce a Cat:

cat :: Parser Animal
cat = string "cat" >> pure Cat
Let’s test it:

> parse cat "cat"
Result >< Cat
Ditto dogs and camels:

dog, camel :: Parser Animal
dog = string "dog" >> pure Dog
camel = string "camel" >> pure Camel
And now a parser for our full grammar:

animal :: Parser Animal
animal = cat <|> dog <|> camel
Some tests:

> parse animal "cat"
Result >< Cat
> parse animal "dog"
Result >< Dog
> parse animal "camel"
Result >< Camel
What’s really cool about this is that obviously the strings “cat” and “camel” overlap at the start. Our alternative parser (<|>) effectively backtracks when the cat parser fails before eventually succeeding with the camel parser. In an imperative style program this kind of logic would result in much messier code.

Exercises
Make a parser stringTok which uses the string parser to parse a given string, but ignores any spaces before or after the token.
Write some messy imperative-style JavaScript (no higher-order functions allowed) to parse cat, dog or camel and construct a different class instance for each.
Now add “dolphin” to the grammar, and use a stopwatch to time yourself extending your messy imperative code. I bet it takes longer than extending the animal parser combinator.
Modify the grammar and the ADT to have some extra data fields for each of the animal types, e.g. humpCount, remainingLives, barkstyle, etc.
Extend your parser to produce these records.
Creating a Parse Tree
Programs are usually parsed into a tree structure called an Abstract Syntax Tree (AST), more generally known as a parse tree. Further processing ultimately into an object file in the appropriate format (whether it’s some sort of machine code directly executable on the machine architecture or some sort of intermediate format—e.g. Java bytecode) then essentially boils down to traversal of this tree to evaluate the statements and expressions there in the appropriate order.

We will not implement a parser for a full programming language, but to at least demonstrate what this concept looks like in Haskell we will create a simple parser for simple arithmetic expressions. The parser generates a tree structure capturing the order of operations, which we may then traverse to perform a calculation.

To start with, here is a BNF grammar for a simple calculator with three operations *, + and -, with * having higher precedence than + or -:

<expr> ::= <term> | <expr> <addop> <term>
<term> ::= <number> | <number> "*" <number>
<addop> ::= "+" | "-"
An expression <expr> consists of one or more <term>s that may be combined with an <addop> (an addition operation, either "+" or "-"). A <term> involves one or more numbers, multiplied together.

The dependencies between the non-terminal expressions makes explicit the precedence of multiply operations needing to occur before add (and subtract).

The data structure we will create uses the following Algebraic Datatype:

data Expr = Plus Expr Expr
          | Minus Expr Expr
          | Times Expr Expr
          | Number Integer
  deriving Show
Our top-level function will be called parseCalc:

parseCalc :: String -> ParseResult Expr
parseCalc = parse expr
And an example use might look like:

> parseCalc " 6 *4 + 3- 8 *  2"
Result >< Minus (Plus (Times (Number 6) (Number 4)) (Number 3)) (Times (Number 8) (Number 2))
Here’s some ASCII art to make the tree structure of the ParseResult Expr more clear:

Minus
 ├──Plus
 |   ├──Times
 |   |   ├──Number 6
 |   |   └──Number 4
 |   └──Number 3
 └──Times
     ├──Number 8
     └──Number 2
Exercises
make an instance of show for Expr which pretty prints such trees
Make a function which performs the calculation specified in an Expr tree like the one above.
Obviously we are going to need to parse numbers, so let’s start with a simple parser which creates a Number.
Note that whereas our previous parser had type phoneNumber :: Parser [Char]—i.e. it produced strings—this, and most of the parsers below, produces an Expr.

number :: Parser Expr
number = spaces >> Number . read . (:[]) <$> digit
We keep things simple for now, make use of our existing digit parser, and limit our input to only single digit numbers.
The expression Number . read . (:[]) is fmapped over the Parser Char returned by digit.
We use the Prelude function read :: Read a => String -> a to create the Int expected by Number. Since read expects a string, we apply (:[]) to turn the Char into [Char], i.e. a String.

Next, we’ll need a parser for the various operators (*,+ and -). There’s enough of them that we’ll make it a general purpose Parser Char parameterised by the character we expect:

op :: Char -> Parser Char -- parse a single char operator
op c = do
   spaces
   is c
   pure c
As before, spaces ignores any number of ' ' characters.

Here’s how we use op for *; note that it returns only the Times constructor. Thus, our return type is an as-yet unapplied binary function (and we see now why (<*>) is going to be useful).

times :: Parser (Expr -> Expr -> Expr)
times = op '*' >> pure Times
And for + and - a straightforward implementation of the <addop> non-terminal from our grammar:

addop :: Parser (Expr -> Expr -> Expr)
addop = (op '+' >> pure Plus) <|> (op '-' >> pure Minus)
And some more non-terminals:

expr :: Parser Expr
expr = chain term addop

term :: Parser Expr
term = chain number times
These use the chain function to handle repeated chains of operators (*, -, +) of unknown length. We could make each of these functions recursive with a <|> to provide an alternative for the base case end-of-chain (as we did for spaces, above), but we can factor the pattern out into a reusable function, like so:

chain :: Parser a -> Parser (a->a->a) -> Parser a
chain p op = p >>= rest
   where
   rest :: a -> Parser a
   rest a = (do
               f <- op
               b <- p
               rest (f a b)
            ) <|> pure a
But, how does chain work?

p >>= rest: The parser p is applied, and we pass this parsed value, to the function call rest

rest a: Within the rest function, the parser op is applied to parse an operator f, and the parser p is applied again to parse another value b. The result is then combined using the function f applied to both a and b to form a new value. The rest function is then called recursively, with this new value.

Recursive calls: The recursive calls continue until there are no more operators op to parse, at which point the parser returns the last value a. This is achieved using the pure a expression. This makes the function tail recursive

This gives us a way to parse expressions of the form “1+2+3+4+5” by parsing “1” initially, using p then repeatedly parsing something of the form “+2”, where op would parse the “+” and the p would then parse the “2”. These are combined using our Plus constructor to be of form Plus 1 2, this will then recessively apply the p and op parser over the rest of the string: “+3+4+5”.

But, can we re-write this using a fold?

chain :: Parser a -> Parser (a -> a -> a) -> Parser a
chain p op = foldl applyOp <$> p <*> many (liftA2 (,) op p)
  where
    applyOp :: a -> (a->a->a, a) -> a
    applyOp x (op, y) = op x y
foldl applyOp <$> p: This part uses the Functor instances to combine the parsed values and apply the operators in a left-associative manner. foldl applyOp is partially applied to p, creating a parser that parses an initial value (p) and then applies the left-associative chain of operators and values.

many ((,) <$> op <*> p): This part represents the repetition of pairs (op, p) using the many combinator. The tuple structure here just allows us to store the pairs of op and p. We use liftA2 to lift both parse results in to the tuple constructor. We run this many times, to parse many pairs of op and p, and create a list of tuples. As a result, it creates a parser that parses an operator (op) followed by a value (p) and repeats this zero or more times.

applyOp x (op, y): This function is used by foldl to combine the parsed values and operators. It takes an accumulated value x, an operator op, and a new value y, and applies the operator to the accumulated value and the new value.

Exercises
Similar to chain, factor out the recursion of spaces into a function which returns a parser that continues producing a list of values from a given parser, i.e. list :: Parser a -> Parser [a].
Parsing Rock-Paper-Scissors
A common use-case for parsing is deserialising data stored as a string. Of course, there are general data interchange formats such as JSON and XML for which most languages have parsers available. However, sometimes you want to store data in your own format for compactness or readability, and when you do, deserialising the data requires a custom parser (this example is contributed by Arthur Maheo).

We will explore a small game of Rock-Paper-Scissors using a memory. The play function will have the following type:

data RockPaperScissors = Rock | Paper | Scissors

-- | Play a round of RPS given the result of the previous round.
play
  :: Maybe (RockPaperScissors, RockPaperScissors, String)
  -- ^ Result of the previous round as: (your choice, opponent choice, your memory)
  -> (RockPaperScissors, String) -- ^ (Choice, new memory)
We will build a simple player which will keep track of the opponent’s previous choices and try to counter the most common one.

How to build a memory
We will convert to string using a simple Show instance:

instance Show RockPaperScissors where
  show :: RockPaperScissors -> String
  show Rock = "R"
  show Paper = "P"
  show Scissors = "S"
(Note, we could also define a Read instance to deserialise such a simple type but we are going to define a ParserCombinator for interest and extensibility to much more complex scenarios).

The straightforward way to create the memory is to just store a list of all the choices made by the opponent. So, for example, if the results from the previous three rounds were:

(Rock, Paper), (Rock, Scissors), (Paper, Scissors)
Then, a compact memory representation will be: "PSS".

Note: We only store single characters, so we do not need separators, but if you have more complex data, you will want separators.

Reading the memory
Now, we want to define a Parser RockPaperScissors which will turn a string into a choice. First, we will define a parser for each of the three choices:

rock :: Parser RockPaperScissors
rock = is 'R' >> pure Rock

scissors :: Parser RockPaperScissors
scissors = is 'S' >> pure Scissors

paper :: Parser RockPaperScissors
paper = is 'P' >> pure Paper
This will give:

>>> parse rock "R"
Result >< R
>>> parse rock "RR"
Result >R< R
>>> parse rock "P"
Unexpected character: "P"
To combine those parsers, we will use the option parser (<|>).

choice :: Parser RockPaperScissors
choice = rock <|> paper <|> scissors
And, to be able to read a list of choices, we need to use the list parser:

>>> parse choice "PSS"
Result >SS< P
>>> parse (list choice) "PSCS"
Result >CS< [P,S]
>>> parse (list choice) "PSS"
Result >< [P,S,S]
Playing the game
Our decision function will take a list of RockPaperScissors and return the move that would win against most of them. One question remains: how do we get the memory out of the parser? The answer is: pattern-matching.

getMem :: ParseResult a -> a
getMem (Result _ cs) = cs
getMem (Error _) = error "You should not do that!"
Obviously, in a longer program you want to be handling this case better.

Hint: If your parser returns a list of elements, the empty list [] is a good default case.

Putting it all together
The first round, our player will just pick a choice at random and return an empty memory.

play Nothing = (Scissors, "") -- Chosen at random!
Now, we need to write a couple functions:

winAgainst that determines which choice wins against a given one.
mostCommon which finds the most common occurrence in a list.
With that, we have a full play function:

play (Just (_, opponent, mem)) = (winning whole, concatMap convert whole)
  where
    -- Convert the memory to a list of different choices
    as_choices = getMem . parse (list choice)
    -- Get the whole set of moves—all the prev. rounds + last one
    whole = opponent: as_choices mem
    winning = winAgainst . mostCommon
>>> play Nothing
(S,"")
>>> play (Just (Scissors, Scissors, ""))
(R,"S")
>>> play (Just (Scissors, Scissors, "RRP"))
(P,"SRRP")
Note: Here we can see the results directly because RockPaperScissors has an instance of Show. If you want to do the same with a datatype without Show, you would need to call convert.

Going further
Now, this is a simplistic view of storing information. We are only concatenating characters because our data is so small. However, there are better ways to store that data.

One issue with this approach is that we need to process the memory sequentially at each round. Instead, we could keep track of the number of occurrences of each choice.

Exercise
Implement a memory for the following datatype.

data Played = Played {rocks, papers, scissors :: Int}

-- | Store a @Played@ as a string in format: @nC@, with @n@ the number of
-- occurrences and @C@ the choice.
convert' :: Played -> String
convert' Played{rocks, papers, scissors} = 
  show rocks ++ "R" ++ show papers ++ "P" ++ show scissors ++ "S"
>>> play Nothing
(S,"0R0P0S")
>>> play (Just (Scissors, Scissors, "0R0P0S"))
(R,"0R0P1S")
>>> play (Just (Scissors, Scissors, "2R1P0S"))
(P,"2R1P1S")
Glossary
Parser: A program that processes a string of text to extract structured information from it. Parsers are used in interpreting programming languages, data formats, and other structured text formats.

Context-Free Grammar: A type of formal grammar that is used to define the syntax of programming languages and data formats. CFGs consist of a set of production rules that define how terminals and non-terminals can be combined to produce strings in the language.

Backus-Naur Form: A notation for expressing context-free grammars. It is used to formally describe the syntax of programming languages.

Terminal: In the context of grammars, a terminal is a symbol that appears in the strings generated by the grammar. Terminals are the actual characters or tokens of the language.

Non-Terminal: A symbol in a grammar that can be replaced by a sequence of terminals and non-terminals according to the production rules of the grammar.

Parser Combinator: A higher-order function that takes parsers as input and combines them to create new parsers. Parser combinators are used to build complex parsers in a modular and compositional way.

Abstract Syntax Tree: A tree representation of the abstract syntactic structure of a string of text. Each node in the tree represents a construct occurring in the text.


-----------

I want you to do Part A and B first, and focus on building one on top of the other. It must be logically and intuitive to understand and not convoluted, it Must be very easy and straightforward and without any errors, I have also put in additional instructions to help guide you as well, also remember that each output html file should contain the html boilerplate too (i.e <!doctype> etc) and must perfectly match the expected out, including the exact number of spaces and newlines etc:

instructions:

please help me implement this correctly:
we will use Haskell to develop a transpiler that converts Markdown strings into HyperText Markup Language (HTML). This task involves parsing Markdown syntax and generating corresponding HTML output. A web page is provided, in which Markdown will be sent through an HTML-based websocket connection to a Haskell backend server, the Haskell server will need to convert this Markdown into the corresponding HTML and return it back to the website. A skeleton code was provided which will handle the basic communication between the web page and your assignment code. You are encouraged to utilise materials covered in previous weeks, including solutions for tutorial questions, to aid in the development of your transpiler. You must reference or cite ideas and code constructs obtained from external sources, as well as anything else you might find in your independent research, for this assignment. The assignment is split up into Part A (parsing), Part B (pretty printing) and Part C (extras). However, we do recommend completing Part A/Part B in tandem. The language you will parse will be based on the Markdown specification, however with additional restrictions to reduce ambiguity. It is important that you read the requirements of each exercise carefully to avoid unnecessary work. Goals / Learning Outcomes The purpose of this assignment is to highlight and apply the skills you have learned to a practical exercise (parsing): ● Use functional programming and parsing effectively ● Understand and be able to use key functional programming principles (higher order functions, pure functions, immutable data structures, abstractions) ● Apply Haskell and FP techniques to parse non-trivial Markdown text Scope of assignment You are only required to parse an expression into the necessary data types and convert the result to an HTML string such that it can be rendered using an existing interpreter. You will not be required to render the Markdown or HTML strings.Exercises (24 marks) These exercises provide a structured approach for creating the beginnings of a transpiler. ● Part A (12 marks): Parsing Markdown strings ● Part B (6 marks): Conversion between Markdown and HTML ● Part C (6 marks): Adding extra functionality to the webpage. ● (Extension) Part D Part E: extensions for bonus marks! You must parse the input into an intermediary representation (ADT) such as an Abstract Syntax Tree to receive marks. This will allow easy conversion between your ADT and HTML. You must add deriving Show to your ADT and all custom types your ADT contains. (Note that the skeleton code already has deriving Show on the ADT type for you, which you must not remove.) You must not override this default Show instance as this will help us test your code. Your Assignment.hs file must export the following functions: ● markdownParser :: Parser ADT ● convertADTHTML :: ADT -> String Example Scripts For each of these exercises, there will be a series of provided Markdown files. By running stack test, it will try to parse the Markdown and save the output to a folder. This will generate HTML which you can manually view for correctness in a browser. During marking, we will be running your transpiler on more complex examples than the provided example scripts, therefore, it is important you devise your own test cases to ensure your parser is valid on more complex Markdown. It will also aim to produce a git diff, which is the difference between your output and the expected output. However, this requires installing the git command line tool. So, ensure that it is installed. Furthermore, the more recommended way to test your code will be to use npm run dev in combination with stack run main can be used to run the webpage with a live editor, running your code in real-time.Part A: (12 marks): Parsing Markdown The first part of this task, requires you to parse a markdown string into an Algebraic Data Type (ADT). This requires you to define your own Algebraic Data Type and define a series of functions that parse everything in the requirements. Consider that you will need to convert the result to HTML and therefore, your ADT should have enough information to assist you in converting to HTML. Aside - Text Modifiers (2 marks) There are six different modifiers for inline text, which can change the way a markdown string will be rendered. You do not have to worry about any escape characters. All text modifiers will need to be strictly non-empty. ● Italic Text: Specified by a single underscore character, _. For example, italics ● Bold Text: Specified by a set of two asterisks, **, around a word. For example, bold ● Strikethrough: Specified by two tilde characters, ~~, around a word. For example, strikethrough ● Link: Users can include a link to an external page using link text. For example, click here. You do not need to consider links inside links. ● Inline Code: Users can include code in the middle of sentences, using a backtick character, . For example, there is code` here ● Footnotes: Users can indicate a footnote with [^ℤ
], where ℤ

= {1,2,3,…}, i.e., any positive integer. For example, 1, 2 and so forth. Note that you do not need to validate any sort of ordering on these numbers, e.g., the markdown may only contain one footnote [^10]. You also do not need to validate that the footnote comes with an appropriate reference (see Footnote References). ○ Note that there must not be any whitespace inside the [ and ]. For example, 1, 2, and [ ^3] are all not valid footnotes. You do not need to consider text with nested modifiers, such as bold and italics. Unless specified otherwise, the text inside the modifiers can include any amount of whitespace (excluding new lines). For example, _ italics _, **bold **, ~~ strikethrough~~, inline code, and link text, and [link text] (example.com) are all valid.Images (0.5 marks) An image is specified with three parts:
The Alt Text is the alternative text for the image, which is displayed if the image fails to load or for accessibility purposes.
The URL is the URL or path to the image file. This can be a web URL or a local file path. The URL cannot contain any whitespace.
The Caption Text is the caption for the image. Alt Text The alternative text, caption text, and URL should not consider the text modifiers. An image must be at the beginning of a line, and the exclamation mark (!) character may be preceded by zero or more (non-newline) whitespace characters. There must be at least one non-newline whitespace character between the URL and the caption text. For example, ![Alt Text](URL"Caption Text") is not a valid image. There must not be any spaces after the ! and before the [. Footnote References (0.5 marks) Similarly to footnotes, footnote references consist of at the beginning of a line: ● zero or more (non-newline) whitespace characters, followed by ● [^], where ℤ
= {1,2,3,…}, i.e., any positive integer, followed by ● a colon (:), followed by ● some text. Note that this text will not include the text modifiers. Leading whitespace before the text should be ignored.
Heading 1
Heading 2
Heading 3
Heading 4
Heading 5
Heading 6
This heading has a space before the hash
Note that because at least one non-newline whitespace character is required, this is not a valid heading: #Heading 1. Also, because the line must start with the hash characters (or whitespace), the following is not a valid heading: abc # Heading. Alternatively, Heading 1 and Heading 2 can be specified with an alternative syntax (shown below). On the line below the text, add at least 2 equals sign (=) characters for heading level 1 or at least 2 dash (-) characters for heading level 2. The line below the text must not contain any other characters. There is no alternative syntax for any other heading levels. The heading text, equals sign (=) characters and dash (-) characers may be preceded by zero or more (non-newline) whitespace characters. Alternative Heading 1
Heading level 2
A heading 1 with a space in front of it==== Importantly, headings may include any of the previously mentioned text modifiers, for example, a heading can be bolded, by surrounding it with a double asterisk.

Bolded Heading 1
Blockquotes (1 mark) To create a block quote in Markdown, you use the greater than symbol (>) at the beginning of a line followed by the text you want to quote. The greater than symbol (>) may be preceded by zero or more (non-newline) whitespace characters before it on the same line. You can also include multiple lines of text within the same block quote by starting each consecutive line with the greater than symbol (>). Leading whitespace after the greater than symbol (>) and before the text should be ignored. The text inside the block quote may have text modifiers. You do not need to consider nested blo代 写FIT2102、Java/Python 代做程序编程语言ck quotes. For example:

This is a block quote. It can span multiple lines. This has a space before > and is also a block quote Code (1 mark) A code block in Markdown starts with three backticks (```) on a line by themselves, followed by an optional language identifier. The code block ends with another three backticks on a line by themselves. The code block should not consider the text modifiers. The first three backticks may have zero or more (non-newline) whitespace characters preceding it. An example code block is:

main :: IO ()
main = do
putStrLn "Never gonna give you up"
putStrLn "Never gonna let you down"
putStrLn "Never gonna run around and desert you"
Never gonna let you cryNever gonna say goodbye
Never gonna tell a lie and hurt you
Ordered Lists (2 marks) An ordered list consists of at least one ordered list item separated by exactly 1 new line character. An ordered list item starts with a positive number at the beginning of a line, a . (full stop) character, and at least one whitespace character (excluding new lines). An ordered list must start with the number 1, and any number after that can appear. You do not have to consider any other numbering system or an unordered list. Ordered lists may contain sublists, where there will be exactly 4 spaces before each ordered list item. Each sublist must also start with the number 1. Similar to previous sections, list items may also contain text modifiers.

Item 1
Sub Item 1
Sub Item 2
Sub Item 3
Bolded Item 2
Item 3
Item 4 You do not have to handle unordered lists. Ordered lists must not have any whitespace before the number, unless it is the 4 spaces of indentation for a sublist. For example:
This is an ordered list
This is not an ordered list (starts with 2 spaces) Tables (3 marks) To create a table in Markdown, you use pipes (|) to separate columns and at least three dashes (-) between each column to separate the header row from the content rows. Each column may contain varying amounts of dashes. Each row is written on a separate line. The beginning and ending pipes (|) are compulsory. Each row must have the same amount of columns. Each cell may also contain text with the text modifiers. Leading and trailing whitespace before and after the text in each cell should be ignored. Each row in the table may be preceded by zero or more (non-newline) whitespace characters.| Tables | Are | Cool | | ------------- | ------------- | ----- | | here | is | data | | here | is | data | | here | is also | bolded data | | also | part of the | table | Part B: (6 marks): HTML Conversion The second part of this task requires you to convert your ADT into a HTML representation. The resulting HTML file must be formatted such that it is indented with 4 spaces at the correct level to reflect the tree structure of HTML, ensuring that the HTML is valid and correctly renders the provided markdown. You do not need to indent the text modifiers, but other nested objects should be indented correctly. All HTML generated must be a self-contained webpage, i.e., including the following information, placing all generated HTML within the tags.
Test

GENERATED CONTENT GOES HERE

As a reference for the conversion between markdown and HTML, here will be listed the conversion of all of the examples from above. Text Modifiers (1 mark) ● Italics: italics ● Bold: bold ● Strikethrough: strikethrough ● Link: link text ● Inline Code: code● Footnotes: 1. It is important that you follow this convention precisely, where 1 is the number specified with the footnote, to ensure the footnotes work. Images (0.5 marks) The image must be in an image tag, with the appropriate attributes filled.

Footnote References (0.5 marks) A footnote reference must be encased in a tag, and have the appropriately numbered id. My reference. Another reference. The 2 spaces after the colon should be ignored space before the [ Free Text (0.5 marks) Every line of free text must be encased in tags. You do not need to consider how to handle newlines.

Here is some markdown

More lines here

Text Headings (0.5 marks) Where, the number after the h, contains the level of the heading, for example, in heading level 1: Heading 1 Heading 2 Heading 3 Heading 4 Heading 5 Heading 6 This heading has a space before the hash Alternative Heading 1Heading level 2 A heading 1 with a space in front of it Blockquotes (0.5 marks) Each blockquote must be encased by , while each line within the blockquote must be encased with a tag.

This is a block quote.

It can span multiple lines.

Code (0.5 marks) The code block must be encased in both the and the tags. If there is a language identifier (e.g., haskell), it must be included within the class attribute, prefixed by language-. Otherwise, there should not be any class attribute. The newlines and code indentation must remain. main :: IO () main = do putStrLn "Never gonna give you up" putStrLn "Never gonna let you down" putStrLn "Never gonna run around and desert you"

Never gonna let you cry Never gonna say goodbye Never gonna tell a lie and hurt you

Ordered Lists (1 marks) Ordered lists must begin and end with the tag, and each list item must begin and end with the opening/closing tag.

Item 1

Sub Item 1 Sub Item 2 Sub Item 3

Bolded Item 2 Item 3 Item 4

Tables (1 mark) The HTML convention for representing tables involves using the , , , and elements. represents the entire table, represents a row within the table, represents a header cell within a table row, used for the header row, and represents a data cell within a table row, used for the content rows. You may optionally include and tags. Either of these outupts is acceptable:

Tables Are Cool

here is data

here is data

here is also bolded data

also part of the table

Tables Are Cool

here is data

here is data

here is also bolded data

also part of the table

Part C (6 marks): Adding extra functionality to the webpage This task involves changing the webpage to include extra capabilities allowing a more feature-full UI. You will not be marked on the layout, or ease of use of features, as long as they are clearly visible to your marker, e.g., a button should be clearly visible on the screen. This task will involve some light additions to both the HTML page and TypeScript code. This will likely involve creating an observable stream for the data, merging it into the subscription stream, and sending the information to the Haskell backend. The communicated information between the Haskell backend and the webpage will need to be updated to include additional information that the user wants the engine to achieve. ● A button must be added to the webpage for saving, where the converted HTML is saved using Haskell. The user does not need to be prompted for a file name, and the HTML should be saved according to the current time, formatted in ISO 8601 format for the current date and time: YYYY-MM-DDTHH:MM:SS. The function getTime is provided which will provide you this time in an IO String format. ● A separate input box, to allow the user to change the title of the page, instead of the default Converted HTML.Part D (up to 6 bonus marks): Extension Implement anything that is interesting, impressive, or otherwise “shows off” your understanding of Haskell, Functional Programming, and/or Parsing. To achieve the maximum amount of bonus marks, the feature should be similar in complexity to Part C (6 marks): The bonus marks only apply to this assignment, and the final mark for this assignment is capped at 30 marks (100%). This means you cannot score more than 30 marks or 100%. Some suggestions for extensions of varying complexity and difficulty: ● Markdown validation ○ E.g., enforce all table columns have the same width ● Correct BNF for the Markdown you are parsing in report (worth 2 marks) ○ For any part of the parser which is not context-free, you may simplify the parsing rules to be context-free. ● Further extensions to the webpage for extra features, using RxJS ● Parse nested text modifiers, such as bold and italics and click here ● Parse further parts of the markdown specification which make use of interesting parsers, which you have not used in other parts of the assignment. ● Comprehensive test cases over the parser and pretty printing ○ Warning: It is super hard to be comprehensive, stay away unless you love testing. (Choosing one of the simpler suggestions to implement may not receive the maximum available marks).Report (2 marks) You are required to provide a report in PDF format of max. 600 words (markers will not mark beyond this word limit). Descriptions of extensions can use up to 200 words per extension feature. Make sure to summarise the intention of the code, and highlight the interesting parts and difficulties you encountered. Focus on the "why" not the "how". Additionally, just posting screenshots of code is heavily discouraged, unless it contains something of particular importance. Remember, markers will be looking at your code alongside your report, so we do not need to see your code twice. Importantly, this report must include a description of why and how parser combinators helped you complete the parsing. In summary, your report should include the following sections: ● Design of the code (including data structures) ○ High-level description of approach ○ High-level structure of code ○ Code architecture choices ● Parsing ○ Usage of parser combinators ○ Choices made in creating parsers and parser combinators ○ How parsers and parser combinators were constructed using the Functor, Applicative, and Monad typeclasses ● Functional Programming (focusing on the why) ○ Small modular functions ○ Composing small functions together ○ Declarative style (including point free style) ● Haskell Language Features Used (focusing on the why) ○ Typeclasses and Custom Types ○ Higher order functions, fmap, apply, bind ○ Function composition ● Description of Extensions (if applicable) ○ What you intended to implement ○ What you did implement ○ What is cool/interesting/complex about it ○ This may include using Haskell features that are not covered in course content There is some overlap between the sections. You should avoid repeating descriptions or ideas in the report.Code Quality (4 marks) Code quality will relate more to how understandable your code is. You must have readable and functional code, commented when necessary. Readable code means that you keep your lines at a reasonable length (>=) for the sake of using the Monad when it is not needed will not count as "effective usage." Most importantly, code that does not utilise Haskell's language features, and that attempts to code in a more imperative style, will not be awarded high marks. Minimum Requirements: An estimate of a passing grade will be parsing up to and including code blocks, but not lists or tables, where the difficulty and the marks step up. However, this will need to be accompanied by high code quality and a good report. A higher mark will require parsing of the more difficult data structures, and modifications of the HTML page.Changelog ● Add note that text modifiers must be non-empty ● Add note about BNF can simplify parser, if and only if the parser is not context free. ● 18 Sep: Remove the requirement to parse nested text modifiers and instead make that an extension ● 18 Sep: Fix issue in scaffold where frontend would show output HTML with a leading and trailing quote ● 20 Sep: Changed “Abstract Data Type” to “Algebraic Data Type” (under Part A) ● 24 Sep: Clarify that URLs in images should not consider text modifiers ● 25 Sep: Clarify that there should be no spaces after ! and before [ in images ● 25 Sep: Clarify whitespace rules for images, footnote references, headings, blockquotes, code blocks, and tables ● 25 Sep: Specify how to convert a code block with no language identifier to HTML ● 28 Sep: Allow optionally including and when rendering tables ● 29 Sep: Fix indentation in ordered list HTML output



Additional Instructions:

Hello, and welcome to a getting started guide.

This is the post for you if you are staring at the code bundle or specs and don't know what to do! Compared to the previous assignment, this is a lot more exercise based, rather than developing your own game, you will have to develop a series of parsers for specific purposes.

So, as you open up the code, you will notice two important folders Haskell and JS. The Haskell folder contains a folder called src and will likely contain all the files you will need to be editing for the first two exercises of the assignment. We will come back to the JS folder later. 

When you open up the Assignment.hs, this is the file which requires most of your work. You will notice, there is at a markerdownParser and convertATDHTML functions. These are the parts you will need to be working on for the first two exercises. The ADT type, is set to only have one value Empty, however, this is mostly just a placeholder, and you will be required to change this and likely remove the Empty case. This ADT should be the return type of your parser, and is what will be contained within the ParseResult. You should structure your ADT in a logical manner.

The other files in the src folder, contain the parser which should already be implemented for you. This is a slight extension to the Maybe parser from the labs.

Instead of:

Nothing you have a Error ParseError  which specifies which kind of error.

Instead of

Just (String, a) you have Result String a  Result Input a  

If you run stack test in the Haskell folder this will run each of the files inside examples/inputs and run the parser/prettyprinting over all of the examples. The output can be inspected by looking at examples/outputs to see the output of your pretty printer. We even included it to output the git diff. Once the diff is empty, your code exactly matches the input.

Now, the JS folder. This is a UI to interact with your parser. If you run npm install and npm run dev inside the JS folder, and stack run inside the Haskell folder you will be greeted with a gorgeous UI (designed by yours truly). You can then type markdown in to the LHS and the HTML will appear on the RHS (hopefully). Part of this assignment will be adding slight extensions to the UI such as a save button!

I know what you might be thinking now Okay, cool, test suite and UI super nice. Thanks teaching team for putting that together for me. But how do I run my code manually? Do not forget about GHCi!

parse markdownParser "**2102 rules**" will run your parser on the bolded string 2102 rules. The result will be something of the following form: Result >**2102 rules**< Empty where the text inside > < will be the unparsed input, and the information after that will be the result. 

Here is a line of code you can use in GHCi, which will attempt to parse and run the pretty printing on the result. 

parse (convertADTHTML <$> markdownParser) "**2102 rules**" 


FAQ (This may be expanded upon as we go):

No more doctests?
Unfortunately, no more relying on doctest to see if your parser works. You will be encouraged to use GHCi to run your code and see the results manually. You are welcome to add more doctests to the code as you see fit.

Woah, the Parser and Instances are already implemented?
Yes, these are mainly from the tutorials, so are already given. But, you are more than welcome to add more general purpose parsers as you want! In fact we encourage you too! But, make sure it is clear that you have edited or added files. 

Huh? What is the parser type, no more Maybes?
There is a new parser type, which is overall very similar to the one we have been using, except, it is now a Result (equivalent to the previous Just case) or an Error (equivalent to previous Nothing case). But, by having this Error type, we can specify types of errors which can help provide more informative information than Nothing if your parser fails. Use these errors to your advantage!

Why does the ADT derive Show and Eq?
Here, we asked Haskell to provide definitions for these type classes, so Haskell will know how to convert your ADT to a string and check equality. The string conversion will not be valid HTML, but will give you an idea of the behaviour of your parser. Please do not overwrite this or change the derive Show. We will be using this to isolate testing your parser. 

Can I write more markdown inputs?
Yes, stack test should handle as many things as in the appropriate input folders

What can I import?
Anything you like, as long as it is in base. How do you know if it is in base? The magic of hoogle, search your function name, and see if base is listed. See example below for map, where the word is highlighted. You will lose marks in terms of code quality, if you re-write some of the functions we showed you, for example, if you write your own map on a list. So, please use the existing functions where applicable. 


Comment

Sort by Newest 
Levente Zoltan
4w

Resolved
I recommend everyone to load up Parser.hs in ghci and to test and play around with each parser to get an understanding of what they actually do and how it could be useful :)


10
Reply

Sean Michael Allan Silva
4w

Resolved
Are we intended to import Control.Applicative (Alternative (..)) in Assignment.hs?
I wasn't getting any parser alternatives to work without that import.


1
Reply

Rhys Newbury
4w
Yep. The scaffolds come with basically the minimum set of imports to compile. All others are up to you


Scaffold:

assignment.hs:

module Assignment (markdownParser, convertADTHTML) where


import           Data.Time.Clock  (getCurrentTime)
import           Data.Time.Format (defaultTimeLocale, formatTime)
import           Instances        (Parser (..))
import           Parser           ()

data ADT = Empty
  -- Your ADT **must** derive Show.
  deriving (Show, Eq)

markdownParser :: Parser ADT
markdownParser = pure Empty

getTime :: IO String
getTime = formatTime defaultTimeLocale "%Y-%m-%dT%H:%M:%S" <$> getCurrentTime

convertADTHTML :: ADT -> String
convertADTHTML Empty = "IMPLEMENT_THIS"


Parser.hs:

{-# OPTIONS_GHC -Wno-missing-export-lists #-}

-- | Implementation of a parser-combinator.
module Parser where

import           Control.Applicative
import           Data.Char           (isAlpha, isDigit, isLower, isSpace,
                                      isUpper)
import           Instances           (ParseError (..), ParseResult (..),
                                      Parser (..), readInt)

-- $setup
-- >>> import Instances (isErrorResult, parse)


-- | -------------------------------------------------
-- | --------------- Core parsers --------------------
-- | -------------------------------------------------

-- | Return a parser that always fails with the given error.
--
-- >>> isErrorResult (parse (failed UnexpectedEof) "abc")
-- True
failed :: ParseError -> Parser a
failed = Parser . const . Error

-- | Produces a parser that always fails with 'UnexpectedChar' using the given
-- character.
unexpectedCharParser :: Char -> Parser a
unexpectedCharParser = Parser . const . Error . UnexpectedChar

-- | Return a parser that succeeds with a character off the input or fails with
-- an error if the input is empty.
--
-- >>> parse char "abc"
-- Result >bc< 'a'
--
-- >>> isErrorResult (parse char "")
-- True
char :: Parser Char
char = Parser f
  where
    f ""       = Error UnexpectedEof
    f (x : xs) = Result xs x

-- | Parse numbers as int until non-digit

---- >>> parse int "abc"
-- Result >bc< 'a'
--
-- >>> isErrorResult (parse int "")
-- True
--
-- >>> isErrorResult (parse int "a")
-- True
int :: Parser Int
int = Parser f
  where
    -- This is okay because the case statement is small
    f "" = Error UnexpectedEof
    f x = case readInt x of
      Just (v, rest) -> Result rest v
      Nothing        -> Error $ UnexpectedChar (head x)

-- | Write a parser that asserts that there is no remaining input.
--
-- >>> parse eof ""
-- Result >< ()
--
-- >>> isErrorResult (parse eof "abc")
-- True
eof :: Parser ()
eof = Parser f
  where
    f "" = Result "" ()
    f x  = Error $ ExpectedEof x

-- | -------------------------------------------------
-- | --------------- Satisfy parsers -----------------
-- | -------------------------------------------------
-- | All of these parsers use the `satisfy` parser!
-- | Return a parser that produces a character but fails if:
--
--   * the input is empty; or
--
--   * the character does not satisfy the given predicate.
--
-- >>> parse (satisfy isUpper) "Abc"
-- Result >bc< 'A'
--
-- >>> isErrorResult (parse (satisfy isUpper) "abc")
-- True
satisfy :: (Char -> Bool) -> Parser Char
satisfy f = char >>= f'
  where
    -- This is okay because guards are small
    f' c
      | f c = pure c
      | otherwise = unexpectedCharParser c

-- | Return a parser that produces the given character but fails if:
--
--   * the input is empty; or
--
--   * the produced character is not equal to the given character.
--
-- >>> parse (is 'c') "c"
-- Result >< 'c'
--
-- >>> isErrorResult (parse (is 'c') "")
-- True
--
-- >>> isErrorResult (parse (is 'c') "b")
-- True
is :: Char -> Parser Char
is = satisfy . (==)

-- | Return a parser that produces any character but fails if:
--
--   * the input is empty; or
--
--   * the produced character is equal to the given character.
--
-- >>> parse (isNot 'c') "b"
-- Result >< 'b'
--
-- >>> isErrorResult (parse (isNot 'c') "")
-- True
--
-- >>> isErrorResult (parse (isNot 'c') "c")
-- True
isNot :: Char -> Parser Char
isNot = satisfy . (/=)

-- | Write a function that parses one of the characters in the given string.
--
-- /Hint/: What does `elem` do? What are its parameters?
--
-- >>> parse (oneof "abc") "bcdef"
-- Result >cdef< 'b'
--
-- >>> isErrorResult (parse (oneof "abc") "def")
-- True
oneof :: String -> Parser Char
oneof = satisfy . flip elem

-- | Write a function that parses any character, but fails if it is in the
-- given string.
--
-- /Hint/: What does `notElem` do? What are its parameters?
--
-- >>> parse (noneof "bcd") "abc"
-- Result >bc< 'a'
--
-- >>> isErrorResult (parse (noneof "abcd") "abc")
-- True
noneof :: String -> Parser Char
noneof = satisfy . flip notElem

-- | Return a parser that produces a character between '0' and '9' but fails if
--
--   * the input is empty; or
--
--   * the produced character is not a digit.
--
-- /Hint/: Use the 'isDigit' function
digit :: Parser Char
digit = satisfy isDigit

-- | Return a parser that produces a space character but fails if
--
--   * the input is empty; or
--
--   * the produced character is not a space.
--
-- /Hint/: Use the 'isSpace' function
space :: Parser Char
space = satisfy isSpace

-- | Return a parser that produces a lower-case character but fails if:
--
--   * the input is empty; or
--
--   * the produced character is not lower-case.
--
-- /Hint/: Use the 'isLower' function
lower :: Parser Char
lower = satisfy isLower

-- | Return a parser that produces an upper-case character but fails if:
--
--   * the input is empty; or
--
--   * the produced character is not upper-case.
--
-- /Hint/: Use the 'isUpper' function
upper :: Parser Char
upper = satisfy isUpper

-- | Return a parser that produces an alpha character but fails if:
--
--   * the input is empty; or
--
--   * the produced character is not alpha.
--
-- /Hint/: Use the 'isAlpha' function
alpha :: Parser Char
alpha = satisfy isAlpha

-- | Write a parser that will parse zero or more spaces (including newlines)
--
-- /Hint/: Remember the `space` parser!
--
-- >>> parse spaces " abc"
-- Result >abc< " "
--
-- >>> parse spaces "abc"
-- Result >abc< ""
spaces :: Parser String
spaces = many space

-- | Return a parser that produces one or more space characters (consuming
-- until the first non-space) but fails if:
--
--   * the input is empty; or
--
--   * the first produced character is not a space.
--
-- /Hint/: Remember the `space` parser!
--
-- >>> parse spaces1 " abc"
-- Result >abc< " "
--
-- >>> isErrorResult $ parse spaces1 "abc"
-- True
spaces1 :: Parser String
spaces1 = some space


-- | Write a parser that will parse zero or more spaces (not including newlines)
--
-- The possible whitespace characters: \t, \r, \f, \v, and a space character.
--
-- >>> parse inlineSpace " abc"
-- Result >abc< " "
--
-- >>> parse inlineSpace "abc"
-- Result >abc< ""
inlineSpace :: Parser String
inlineSpace = many (oneof "\t\r\f\v ")

-- | Write a function that parses the given string (fails otherwise).
--
-- /Hint/: Use 'is' and 'traverse'.
--
-- >>> parse (string "abc") "abcdef"
-- Result >def< "abc"
--
-- >>> isErrorResult (parse (string "abc") "bcdef")
-- True
string :: String -> Parser String
string = traverse is

-- | -------------------------------------------------
-- | --------------- Token parsers -------------------
-- | -------------------------------------------------

-- | Write a function that applies the given parser, then parses 0 or more
-- spaces, then produces the result of the original parser.
--
-- /Hint/: You can use the Monad instance or Applicatives
--
-- >>> parse (tok (is 'a')) "a bc"
-- Result >bc< 'a'
--
-- >>> parse (tok (is 'a')) "abc"
-- Result >bc< 'a'
tok :: Parser a -> Parser a
tok = (<* spaces)

-- tok p = do
--   r <- p
--   spaces
--   pure r

-- | Write a function that parses the given char followed by 0 or more spaces.
--
-- /Hint/: Remember the `is` parser
--
-- >>> parse (charTok 'a') "abc"
-- Result >bc< 'a'
--
-- >>> isErrorResult (parse (charTok 'a') "dabc")
-- True
charTok :: Char -> Parser Char
charTok = tok . is

-- | Write a parser that parses a comma ',' followed by 0 or more spaces.
--
-- /Hint/: We just implemented `charTok`
--
-- >>> parse commaTok ",123"
-- Result >123< ','
--
-- >>> isErrorResult( parse commaTok "1,23")
-- True
commaTok :: Parser Char
commaTok = charTok ','

-- | Write a function that parses the given string, followed by 0 or more
-- spaces.
--
-- /Hint/: Remember the `string` parser
--
-- >>> parse (stringTok "abc") "abc  "
-- Result >< "abc"
--
-- >>> isErrorResult (parse (stringTok "abc") "bc  ")
-- True
stringTok :: String -> Parser String
stringTok = tok . string


Instances.hs:

{-# LANGUAGE InstanceSigs #-}

module Instances (ParseResult (Result, Error), Parser (..), readInt, ParseError(..), isErrorResult) where

import           Control.Applicative (Alternative (..))

-- $setup
-- >>> let p = \n -> Parser (\x -> Result x n)
-- >>> let add = \n -> \m -> Parser (\x -> Result x (n+m))

data ParseError
  = UnexpectedEof
  | ExpectedEof Input
  | UnexpectedChar Char
  | UnexpectedString String
  deriving (Eq, Show)

data ParseResult a
  = Error ParseError
  | Result Input a
  deriving (Eq)

type Input = String

newtype Parser a = Parser {parse :: Input -> ParseResult a}

-- Result Instances

instance Show a => Show (ParseResult a) where
  show :: ParseResult a -> String
  show (Result i a) = "Result >" ++ i ++ "< " ++ show a
  show (Error UnexpectedEof) = "Unexpected end of stream"
  show (Error (UnexpectedChar c)) = "Unexpected character: " ++ show [c]
  show (Error (UnexpectedString s)) = "Unexpected string: " ++ show s
  show (Error (ExpectedEof i)) =
    "Expected end of stream, but got >" ++ show i ++ "<"

instance Functor ParseResult where
  fmap :: (a -> b) -> ParseResult a -> ParseResult b
  fmap f (Result i a) = Result i (f a)
  fmap _ (Error e)    = Error e

-- Parser Instances

-- | Functor instance for a parser
--
-- >>> parse ((+1) <$> Parser (`Result` 1)) "hello"
-- Result >hello< 2

--  >>> parse ((+1) <$> Parser (const (Error UnexpectedEof))) "hello"
-- Unexpected end of stream
instance Functor Parser where
  fmap :: (a -> b) -> Parser a -> Parser b
  fmap f (Parser p) = Parser (fmap f . p)

-- | Implement this before Applicative Parser!
--
-- >>> parse (p 1 >>= add 2) ""
-- Result >< 3
--
-- prop> \i j -> parse (p i >>= add j) "" == Result "" (i + j)
instance Monad Parser where
  (>>=) :: Parser a -> (a -> Parser b) -> Parser b
  (>>=) (Parser p) f = Parser $ \i -> case p i of
    Result rest x -> parse (f x) rest
    Error e       -> Error e

-- |
--
-- >>> parse (Parser (`Result` (+1)) <*> Parser (`Result` 1)) "hello"
-- Result >hello< 2
--
-- >>> parse (pure (+1) <*> Parser (`Result` 1)) "hello"
-- Result >hello< 2
--
-- >>> parse (pure (+1) <*> (pure 1 :: Parser Int)) "hello"
-- Result >hello< 2
instance Applicative Parser where
  -- creates a Parser that always succeeds with the given input
  pure :: a -> Parser a
  pure = Parser . flip Result

  -- or
  (<*>) :: Parser (a -> b) -> Parser a -> Parser b
  (<*>) p q = p >>= (<$> q)

-- |
--
-- 'Alternative' is used for parsers that support choice (alternative) and
-- failure (empty). In the context of this 'Parser' type:
--
-- 1. 'empty' represents a parser that always fails
--
-- 2. '<|>' combines two parsers. It tries the first parser on the input,
-- and if it fails it tries the second parser.
--
-- see https://tgdwyer.github.io/haskell3/#alternative
--
-- >>> parse (pure 1 <|> empty) "world, hello!"
-- Result >world, hello!< 1
-- >>> parse (empty <|> pure 1) "world"
-- Result >world< 1
instance Alternative Parser where
  empty :: Parser a
  empty = Parser $ const (Error UnexpectedEof)

  (<|>) :: Parser a -> Parser a -> Parser a
  (<|>) pa pb = Parser $ \x -> case parse pa x of
    Error _ -> parse pb x
    r       -> r

-- Support functions

isErrorResult :: ParseResult a -> Bool
isErrorResult (Error _) = True
isErrorResult _         = False

readInt :: String -> Maybe (Int, String)
readInt s = case reads s of
  [(x, rest)] -> Just (x, rest)
  _           -> Nothing



Main.hs:

{-# LANGUAGE OverloadedStrings #-}

module Main (main) where

-- import Assignment (markdownParser)

import           Assignment              (convertADTHTML, markdownParser)
import           Data.Aeson              (object, (.=))
import           Data.Aeson.Key          (fromString)
import           Data.Text.Lazy          (Text, pack, unpack)
import           Data.Text.Lazy.Encoding (decodeUtf8)
import           Instances               (ParseResult (Result), parse)
import           Web.Scotty              (ActionM, body, json, post, scotty)

getResult :: ParseResult a -> (a -> String) -> String
getResult (Result _ a) f = f a
getResult _ _            = ""

-- Magic code to convert key, value pairs to JSON to send back to the server
jsonResponse :: [(String, String)] -> ActionM ()
jsonResponse pairs =
  json $ object [fromString key .= ((pack value) :: Text) | (key, value) <- pairs]


main :: IO ()
main = scotty 3000 $ do
  post "/api/convertMD" $ do
    requestBody <- body
    -- Convert the raw request body from ByteString to Text
    let requestBodyText = decodeUtf8 requestBody
        -- Convert the Text to String
        str = unpack requestBodyText
        -- Parse the Markdown string using 'markdownParser' and apply 'convertAllHTML'
        converted_html = getResult (parse markdownParser str) convertADTHTML

    -- Respond with the converted HTML as JSON
    jsonResponse [("html", converted_html)]


Spec.hs:

import           Assignment           (convertADTHTML, markdownParser)
import           Control.Exception    (IOException, try)
import           Control.Monad        (mapM_, (>>), (>>=))
import           Data.List            (isPrefixOf)
import           Instances            (ParseResult (Error, Result), parse)
import           System.FilePath      (joinPath, replaceExtension,
                                       splitDirectories, splitFileName,
                                       takeFileName, (</>))

import           System.Directory     (createDirectoryIfMissing)
import           System.FilePath.Glob (glob)
import           System.IO            (IOMode (WriteMode), withFile)
import           System.IO.Error      (isDoesNotExistError)
import           System.Process       (StdStream (UseHandle), createProcess,
                                       proc, std_out, waitForProcess)

-- Function to replace a substring with another substring in a string
replaceSubstring :: String -> String -> String -> String
replaceSubstring _ _ [] = []
replaceSubstring from to str@(x : xs)
  | from `isPrefixOf` str = to ++ replaceSubstring from to (drop (length from) str)
  | otherwise = x : replaceSubstring from to xs

processFile :: FilePath -> FilePath -> IO ()
processFile inputFile outputFile  = do
  putStrLn $ "Starting " ++ inputFile
  result <- try (readFile inputFile) :: IO (Either IOException String)
  case result of
    Left e
      | isDoesNotExistError e -> putStrLn $ "File not found: " ++ inputFile
      | otherwise -> putStrLn $ "Error reading file " ++ inputFile ++ ": " ++ show e
    Right contents -> do
      let parsed = parse markdownParser contents
      case parsed of
        Result _ adt -> do
          let prettyOutput = convertADTHTML adt
          writeFile outputFile prettyOutput
          putStrLn $ "Processed: " ++ inputFile
        _ -> putStrLn $ "Invalid ParseResult for file " ++ inputFile

mkFolderIfNotExists :: FilePath -> IO ()
mkFolderIfNotExists = createDirectoryIfMissing True


gitDiffNoIndex :: FilePath -> FilePath -> IO ()
gitDiffNoIndex file1 file2 = do
    mkFolderIfNotExists "./examples/diff_output"
    let outputFile = genOutputName "diff_output" "diff" file1

    withFile outputFile WriteMode $ \handle -> do
      -- Create a process for git diff --no-index
      (_, _, _, processHandle) <- createProcess (proc "git" ["--no-pager", "diff", "--no-index", "--no-ext-diff", file1, file2])
                                                   { std_out = UseHandle handle }


      -- Wait for the process to complete but ignore the exit code
      _ <- waitForProcess processHandle
      return ()

genOutputName :: FilePath -> String -> String -> FilePath
genOutputName outputFolder extension file = replaceExtension (replaceFolderAtIndex file 1 outputFolder) extension

replaceFolderAtIndex :: FilePath -> Int -> String -> FilePath
replaceFolderAtIndex filePath index newFolder = joinPath (replaceAtIndex index newFolder (splitDirectories dirPath)) </> fileName
  where
    -- Split the file path into directory and file components
    dirPath = fst $ splitFileName filePath
    fileName = takeFileName filePath

    -- Replace the folder at the specified index using zipWith
    replaceAtIndex :: Int -> String -> [FilePath] -> [FilePath]
    replaceAtIndex idx newVal = zipWith (\i folder -> if i == idx then newVal else folder) [0..]

checkADTShow :: IO ()
checkADTShow = do
  let markdownStr = "test **bold**"
  putStrLn "Testing ADT's Show instance:"
  putStrLn $ "Input string: " ++ markdownStr
  putStrLn $ case parse markdownParser markdownStr of
    Error _      -> "Parse error"
    Result _ adt -> "Result: " ++ show adt

main :: IO ()
main = do
  checkADTShow

  putStrLn ""
  putStrLn "Testing example inputs:"
  files <- glob "examples/input/*.md"
  let outputFiles = map (genOutputName "output" "html") files
  let expectedOutput = map (genOutputName "expected_output" "html") files

  mapM_ (uncurry processFile) (zip files outputFiles)
  mapM_ (uncurry gitDiffNoIndex) (zip expectedOutput outputFiles)





Below are the Html, css and js files:

Main.ts:

import { fromEvent, merge } from "rxjs";
import { map, mergeScan, first } from "rxjs/operators";
import { ajax } from "rxjs/ajax";
import { type Observable } from "rxjs";
import { State } from "./types";

import hljs from "highlight.js/lib/core";

import javascript from "highlight.js/lib/languages/javascript";
import python from "highlight.js/lib/languages/python";
import haskell from "highlight.js/lib/languages/haskell";

// Load the languages from the unit for syntax highlighting!
hljs.registerLanguage("javascript", javascript);
hljs.registerLanguage("python", python);
hljs.registerLanguage("haskell", haskell);

const markdownInput = document.getElementById(
    "markdown-input",
) as HTMLTextAreaElement;
const checkbox = document.querySelector('input[name="checkbox"]')!;

type Action = (_: State) => State;

const resetState: Action = (s) => {
    return { ...s, save: false };
};

const compose =
    <T, U>(g: (_: T) => U) =>
    <V>(f: (_: U) => V) =>
    (t: T): V =>
        f(g(t));

// Create an Observable for keyboard input events
const input$: Observable<Action> = fromEvent<KeyboardEvent>(
    markdownInput,
    "input",
).pipe(
    map((event) => (event.target as HTMLInputElement).value),
    map((value) => (s) => ({ ...s, markdown: value })),
);

const checkboxStream$: Observable<Action> = fromEvent(checkbox, "change").pipe(
    map((event) => (event.target as HTMLInputElement).checked),
    map((value) => (s) => ({ ...s, renderHTML: value })),
);

function getHTML(s: State): Observable<State> {
    // Get the HTML as a stream
    return ajax<{ html: string }>({
        url: "/api/convertMD",
        method: "POST",
        headers: {
            "Content-Type": "application/x-www-form-urlencoded",
        },
        body: s.markdown,
    }).pipe(
        map((response) => response.response), // Extracting the response data
        map((data) => {
            return {
                ...s,
                HTML: data.html,
            };
        }),
        first(),
    );
}

const initialState: State = {
    markdown: "",
    HTML: "",
    renderHTML: true,
    save: false,
};

function main() {
    // Subscribe to the input Observable to listen for changes
    const subscription = merge(input$, checkboxStream$)
        .pipe(
            map((reducer: Action) => {
                // Reset Some variables in the state in every tick
                const newReducer = compose(reducer)(resetState);
                return newReducer;
            }),
            mergeScan((acc: State, reducer: Action) => {
                const newState = reducer(acc);
                // getHTML returns an observable of length one
                // so we `scan` and merge the result of getHTML in to our stream
                return getHTML(newState);
            }, initialState),
        )
        .subscribe((value) => {
            const htmlOutput = document.getElementById("html-output");
            if (htmlOutput) {
                htmlOutput.innerHTML = "";
                htmlOutput.textContent = "";
                if (value.renderHTML) {
                    const highlight =
                        '<link rel="stylesheet" href="https://unpkg.com/@highlightjs/cdn-assets@11.3.1/styles/default.min.css" />';
                    htmlOutput.innerHTML = highlight + value.HTML;
                    // Magic code to add code highlighting
                    const blocks = htmlOutput.querySelectorAll("pre code");
                    blocks.forEach((block) =>
                        hljs.highlightElement(block as HTMLElement),
                    );
                } else {
                    htmlOutput.textContent = value.HTML;
                }
            }
        });
}
if (typeof window !== "undefined") {
    window.onload = function () {
        main();
    };
}


types.ts:

export type State = Readonly<{
    markdown: string;
    HTML: string;
    renderHTML: boolean;
    save: false;
}>;


style.css:

body {
    font-family: Arial, sans-serif;
    margin: 0;
    padding: 0;
}

header,
footer {
    background-color: #333;
    color: #fff;
    padding: 10px;
    text-align: center;
}

main {
    padding: 20px;
}

h1,
h2 {
    margin-bottom: 10px;
}

#container {
    display: flex;
    flex-direction: row;
    /* Ensure the sections are laid out horizontally */
    justify-content: space-between;
}

textarea {
    flex: 1;
    /* Take up available space equally */
    height: 200px;
    padding: 10px;
    border: 1px solid #ccc;
    border-radius: 5px;
    resize: vertical;
}

#html-output {
    flex: 1;
    /* Take up available space equally */
    margin-left: 10px;
    /* Add some space between input and output */
    border: 1px solid #ccc;
    border-radius: 5px;
    padding: 10px;
    min-height: 100px;
}

footer {
    margin-top: 20px;
    background-color: #333;
    color: #fff;
    padding: 10px;
    text-align: center;
    position: fixed;
    bottom: 0;
    width: 100%;
}

index.html:

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Markdown to HTML Converter</title>
    <link rel="stylesheet" href="/style.css">
</head>

<body>
    <header>
        <h1>Markdown to HTML Converter</h1>
    </header>

    <main>
        <div id="container" style="display: flex; width: 100%;">
            <section id="input-section" style="flex: 1; padding-right: 10px;">
                <h2>Enter Markdown:</h2>
                <textarea id="markdown-input" placeholder="Enter your Markdown here..." style="width: 100%;"></textarea>
            </section>
            <section id="output-section" style="flex: 1; padding-left: 10px;">
                <h2>HTML Output:</h2>
                <div id="html-output"></div>
                <label><input type="checkbox" name="checkbox" checked>Render HTML</label>
            </section>
        </div>
    </main>
    <footer>
        <p>Developed by Your Name</p>
    </footer>
    <script src="./src/main.ts" type="module"></script>
</body>

</html>