Wednesday, April 11, 2007

DAWG Assignment

The purpose of the second assignment is to allow you to play with some of OCaml's imperative features, while further increasing your exposure to the language. The high level idea is to build a trie to store a list of words and then enable searching of this data structure. For those feeling more ambitious, the next step would be to convert the trie into a DAWG by merging common suffixes.

Your program should:
* Prompt for a filename
* Read all the word from that file
* Build the trie and/or DAWG
* Allow the user to query the data structure

Statistics about node counts (especially for the DAWG) would be neat, too.

For those interested in the value restriction mentioned in class today, there's a paper by entitled Simple Imperative Polymorphism by Andrew Wright which describes the various issues associated with static typing and imperative programming. It's available here in the handy-dandy ps.gz format (please let me know if you can locate a PDF).


Post a Comment

<< Home