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

[Dominik Bollmann]

Just a short update, in case anyone reads along. I found the the problem
with question (2) from the previous mail: My Arbitrary instance for
TrieS was simply wrong and sometimes looped forever, which caused the
program to hang. Besides I found another bug (prefixes of words were
always found as well) which I've fixed now.

The updated code is here: http://lpaste.net/180994

Anyhow, if anyone has any suggestions on how to improve the code
style-wise, etc., I would be very happy to hear them!

Cheers, Dominik.

Dominik Bollmann <dominikbollmann at gmail.com> writes:

> 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.