Stanford CS240h Lab 1

You will write a simple function that performs glob matching Glob matching is a simple form of pattern matching (i.e., regular expressions but greatly reduced).

The function should have the type:

    type GlobPattern = String

    matchGlob :: GlobPattern -> String -> Bool

Where the first argument will be the glob pattern and the second argument will be the string to match on. The function should return True if the string matches the glob.

You are encouraged to use only the base package of Haskell for this lab. So hand roll a parser yourself.

We are providing a skeleton Cabal project to help get started, download it from here.

Due Date

Lab 1 should be submitted by the start of class (12:50pm) on Tuesday, April 8th.

You have 48 hours of late days for the three labs. They are consumed in 24 hour blocks and are used automatically. After they are used, you'll have the maximum grade you can receive for a late lab reduced by 25% each day.

Glob Matching

Your glob matcher should handle any combination of the following patterns:

Literal Matching

Initially parsing the glob pattern you treat all characters as literal except for ?, *, \ and [. So the following glob patterns are exact matchers:

Note that we don't treat ] as a special character unless we are trying to close a set match.

Escaped Literals

All special symbols can also be escaped (just as regular characters can be), giving us the following glob patterns that are also exact matches:

Set Match

When parsing a glob pattern, when you find an unescaped '[' then you need to parse the pattern from that point on as a set match. A range group is closed by the first unescaped ']'.

Please note that set matches can't nest, which means that once a set match has started, the '[' character should be treated as a literal, not a special symbol any more. For example:

A set match specifies a set of characters valid for matching the next character in the string we're matching on. It matches one character only.

Set matches work as follows:

This suggest then that set match be parsed as follows:

Please note that if you end up with an empty set match, either because it is just empty ("[]") or only contains empty ranges, then this can't match anything in a string and so the whole glob pattern can't match any string.


Ranges have some subtle cases. The simple form is: "<char_1>-<char_2>", for example "a-z" adds all characters between 'a' to 'z' to our set match. A set match can contain multiple ranges.

The corner cases though are:

Ranges should simply use the Haskell built-in Ord instance for Char for determining the range.

You may also end up with a range that is empty (i.e., "[z-a]").


So for example:

Cabal -- Build & Test Tool

Cabal is the standard build and packaging tool for Haskell. A starting framework is provided for you. You can find the user guide for Cabal here.

Provided Files

The files provided to get started are:

Building Lab 1

To get up and running (using Cabal), issue the following commands:

    cabal sandbox init

This will initiate a self-contained build environment where any dependencies you need are installed locally in the current directory. This helps avoid the Haskell equivalent of 'DLL Hell!'. If your version of cabal is older such that it doesn't have the sandbox command, then just proceed without it and it should all be fine.

Next, you want to build the lab. For that, issue the following commands:

    cabal install --only-dependencies --enable-tests
    cabal configure --enable-tests
    cabal build

After that, you should also be able to run the test harness simply by typing:

    cabal test

And you'll get some pretty output!

Testing Lab 1

Some skeleton code for a test framework is provided in TestHarness.hs. You'll need to edit it to add your own tests. The test framework uses a Haskell package called hspec. Please refer to it for documentation on how to use it.


While we strongly encourage you to take testing seriously and write a comprehensive test suite, we are only going to grade you on your glob matching implementation.

Grading will be just done on functionality but we will try to give feedback on your coding style.


First, simply type:

    cabal sdist

This will generate a tar file of your code in dist/globber.tar.gz.

Then go to and submit your work through the online form. You can resubmit as many times as you want up until the deadline.

If you have any trouble submitting on-line, then please email the staff mailing .