Nullable

In this part of the assignment, we will implement a function to check whether a regular expression is nullable.

To do

1. The file src/Regex.hs contains a data type Regex for representing (extended) regular expressions as symbolic trees. Read the definition to make sure you understand it.

2. The file src/Evaluation.hs contains a partial implementation of regular-expression derivatives. In this file, complete the implementation of the nullable function. Use the equations from the course materials or the Owens et al. paper.

Hints / Comments

• I found the Haskell built-in functions any, all, and not to be useful.

• There are also a few tests in the file test/NullableSpec.hs. You can run just these tests with the command:

  stack test --test-arguments "--match /Nullable"

• Feel free to add more tests!