[Haskell-beginners] Basic Trie Implementation: Request for Feedback and QuickCheck Question

[Dominik Bollmann]

Hello Haskellers,

I just finished implementing a very simple Trie module, consisting of a
Trie data type as well as operations `insert` and `lookup`. Function
`insert` inserts a new element into the Trie; function lookup searches
for all words in the Trie that match a specific pattern. Besides regular
words, a pattern may consist of a single dot '.', indicating that at
this position of the search term any letter may occur. For example a
pattern "hello" would just search for the word "hello" in the Trie,
while ".ello" would search words starting in *any* letter and followed
by the sequence "ello" (i.e., it searches for "hello", "Hello", "Aello",
etc.)

The code for the Trie module can be found here: http://lpaste.net/180768.

Regarding the code I have two questions:

  (1) Since I'm new to Haskell, I'd very much welcome feedback on the
      general implementation of the Trie module and its two methods what
      I could improve.

  (2) While testing the Trie module with QuickCheck, I wrote the
      property `prop_insert_then_lookup_succeeds` stating that after
      inserting a word into a Trie it can always successfully be looked
      up again. While quickchecking this property seems to succeed, I
      cannot verbose check it. In particular, when I run

      `verboseCheck prop_insert_then_lookup_succeeds`

      this property consumes all my main memory and results in the
      program hanging.

      Does anyone know what I messed up in devising the quickcheck
      property? I guess I left open some memory leak... Maybe it has to
      to with the Arbitrary instance which I might have defined
      incorrectly?

Responses to any of the two questions above are very welcome :-)

Thanks!

Dominik.