Basic Trie Implementation: Request for Feedback and QuickCheck Question
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.
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
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.
participants (1)
-
Dominik Bollmann