Please solve the following question using Haskell

Problem Description In this project, you will write a simple Haskell program to solve the following problem: You are given a maze of h x w cells and you are to find a path from the top-left cell to the bottom-right cell. The input specifies whether there's a wall between adjacent cells. The path must not cross any walls and must not visit any cell more than once. The following is an example: In general, the maze is not necessarily square. However, the maze is connected and contains no cycles. In particular, there always exists a path from the start cell to the end cell and there is exactly one such path that does not visit any cell more than once. Thus, depth-first search or breadth-first search is an appropriate search strategy to find the path. Since there are no cycles in the maze, any path you follow has no way to double back on itself if you don't immediately go back to the cell you just came from. This simplifies the search process significantly because you do not need to keep track of the complete list of cells you have already visited. The input to your program is given as a binary file in the following format: The first four bytes store the height of the maze as a little-endian integer, that is, the bytes of this 4-byte integer are stored in the order from least significant byte to most significant byte. The next four bytes store the width of the maze as a little-endian integer. The remaining bytes represent the walls between cells: - The outside walls of the maze are always present and thus are not represented as part of the input. - Any inside wall of the maze is between two cells of the maze and thus has a cell to its left (for a vertical wall) or a cell above it (for a horizontal wall). Thus, we store two bits for every cell: * The lower bit is 1 if and only if the cell is not in the rightmost column and there is a wall to its right. * The upper bit is 1 if and only if the cell is not in the bottom row and there is a wall below it. We number the bytes encoding the cells in order, starting from 0, and use these byte numbers to number the bits. For each byte, let its least significant bit be bit 0 and its most significant bit be bit 7. Then the jth bit in the ith byte has number 8i + j. If the maze has height h and width w, then the two bits representing the cell in row r and column c are the bits with numbers 2(rw+c) and 2(rw+c)+1. Row and column numbers also count from 0. As an example, the file encoding the maze above has the content 05 00 00 00 05 00 00 00 30 1C 4B C9 86 00 00, where the byte values are written in hexadecimal format here. Your program should read and decode this binary input, compute a path through the maze, and output the path it computes to a file. The output should list the visited cells in order with one cell per line. Each cell should be represented by two integers. The first one is the row of the cell, counting from top to bottom, starting with zero; the second one is the column of the cell, counting from left to right, starting with zero. The output for the maze above thus looks like this: OOH OHHHHCM 4.4. Note that the output file should be a plain text file, not a binary file. Your Task Write a Haskell program to be run from the command line. It takes two arguments: the name of the maze file to be read and the name of the file to write the solution to. Your program should find a path through the maze given in the input file as specified in the problem description and write the result to the file given as the output file. You may assume that the input file to be read is small enough to be read into memory in its entirety. (If that's not the case, you have much bigger problems because the program-internal representation of the maze is likely much bigger than the compact representation in the input file.) Apart from the code needed to parse command line arguments, read the input, and write the output, your solution should be implemented purely functionally. Specifically, you should define an appropriate type Maze representing a maze and an appropriate type Path representing a path through the maze. The conversion of the binary input file into a Maze should be achieved using a pure function of type decodeMaze :: ByteString -> Maybe Maze. The computation of a path should be achieved using a pure function of type findPath :: Maze -> Maybe Path. After reading the input, your ID code should call these functions to decode the input and com- pute the path. The functions have Maybe return types because the input may not be a valid maze file meeting the expectations above. Thus, it is possible that the decoding process fails. Even if it succeeds, the decoded maze may not have a path from the start to the end. In these cases, the functions should fail by returning Nothing. The type signatures of decodeMaze and findPath prevent them from using 10 actions. They do not prevent them from using the ST monad in their implementations. Do not use the ST monad. If you think it is helpful, you are allowed to use the State monad, Maybe monad, and other monads that are nothing more than devices to structure purely functional code more conveniently. (My sample solution uses the list monad, which I mentioned in the lab notes but did not discuss in detail. You do not need the list monad, but it makes things just a tiny bit cleaner.) Your program should run in linear time in the size of the maze, that is, in the number of cells in the maze. Problem Description In this project, you will write a simple Haskell program to solve the following problem: You are given a maze of h x w cells and you are to find a path from the top-left cell to the bottom-right cell. The input specifies whether there's a wall between adjacent cells. The path must not cross any walls and must not visit any cell more than once. The following is an example: In general, the maze is not necessarily square. However, the maze is connected and contains no cycles. In particular, there always exists a path from the start cell to the end cell and there is exactly one such path that does not visit any cell more than once. Thus, depth-first search or breadth-first search is an appropriate search strategy to find the path. Since there are no cycles in the maze, any path you follow has no way to double back on itself if you don't immediately go back to the cell you just came from. This simplifies the search process significantly because you do not need to keep track of the complete list of cells you have already visited. The input to your program is given as a binary file in the following format: The first four bytes store the height of the maze as a little-endian integer, that is, the bytes of this 4-byte integer are stored in the order from least significant byte to most significant byte. The next four bytes store the width of the maze as a little-endian integer. The remaining bytes represent the walls between cells: - The outside walls of the maze are always present and thus are not represented as part of the input. - Any inside wall of the maze is between two cells of the maze and thus has a cell to its left (for a vertical wall) or a cell above it (for a horizontal wall). Thus, we store two bits for every cell: * The lower bit is 1 if and only if the cell is not in the rightmost column and there is a wall to its right. * The upper bit is 1 if and only if the cell is not in the bottom row and there is a wall below it. We number the bytes encoding the cells in order, starting from 0, and use these byte numbers to number the bits. For each byte, let its least significant bit be bit 0 and its most significant bit be bit 7. Then the jth bit in the ith byte has number 8i + j. If the maze has height h and width w, then the two bits representing the cell in row r and column c are the bits with numbers 2(rw+c) and 2(rw+c)+1. Row and column numbers also count from 0. As an example, the file encoding the maze above has the content 05 00 00 00 05 00 00 00 30 1C 4B C9 86 00 00, where the byte values are written in hexadecimal format here. Your program should read and decode this binary input, compute a path through the maze, and output the path it computes to a file. The output should list the visited cells in order with one cell per line. Each cell should be represented by two integers. The first one is the row of the cell, counting from top to bottom, starting with zero; the second one is the column of the cell, counting from left to right, starting with zero. The output for the maze above thus looks like this: OOH OHHHHCM 4.4. Note that the output file should be a plain text file, not a binary file. Your Task Write a Haskell program to be run from the command line. It takes two arguments: the name of the maze file to be read and the name of the file to write the solution to. Your program should find a path through the maze given in the input file as specified in the problem description and write the result to the file given as the output file. You may assume that the input file to be read is small enough to be read into memory in its entirety. (If that's not the case, you have much bigger problems because the program-internal representation of the maze is likely much bigger than the compact representation in the input file.) Apart from the code needed to parse command line arguments, read the input, and write the output, your solution should be implemented purely functionally. Specifically, you should define an appropriate type Maze representing a maze and an appropriate type Path representing a path through the maze. The conversion of the binary input file into a Maze should be achieved using a pure function of type decodeMaze :: ByteString -> Maybe Maze. The computation of a path should be achieved using a pure function of type findPath :: Maze -> Maybe Path. After reading the input, your ID code should call these functions to decode the input and com- pute the path. The functions have Maybe return types because the input may not be a valid maze file meeting the expectations above. Thus, it is possible that the decoding process fails. Even if it succeeds, the decoded maze may not have a path from the start to the end. In these cases, the functions should fail by returning Nothing. The type signatures of decodeMaze and findPath prevent them from using 10 actions. They do not prevent them from using the ST monad in their implementations. Do not use the ST monad. If you think it is helpful, you are allowed to use the State monad, Maybe monad, and other monads that are nothing more than devices to structure purely functional code more conveniently. (My sample solution uses the list monad, which I mentioned in the lab notes but did not discuss in detail. You do not need the list monad, but it makes things just a tiny bit cleaner.) Your program should run in linear time in the size of the maze, that is, in the number of cells in the maze