Hi... I was writing some code yesterday to walk over a directory tree, and needed a Trie. Not seeing one around, I wrote a basic implementation of the functions I needed (attached below). Has anyone else done this? Should I polish it up and offer it for inclusion in Data? --KW 8-)
On Fri, Feb 11, 2005 at 11:28:11AM +0000, Keith Wansbrough wrote:
Hi... I was writing some code yesterday to walk over a directory tree, and needed a Trie. Not seeing one around, I wrote a basic implementation of the functions I needed (attached below).
Has anyone else done this? Should I polish it up and offer it for inclusion in Data?
Yes, definitely! I have implemented Trie's in Haskell about three times, each time with a slightly different interface :) Your module looks very nice. It has many natural functions I haven't thought about. Could you also include a function: insert :: Ord k => [k] -> (Maybe v -> v) -> Trie k v -> Trie k v or insert :: Ord k => [k] -> (Maybe v -> Maybe v) -> Trie k v -> Trie k v Best regards, Tomasz -- Szukamy programisty C++ i Haskell'a: http://tinyurl.com/5mw4e
Keith Wansbrough
Hi... I was writing some code yesterday to walk over a directory tree, and needed a Trie. Not seeing one around, I wrote a basic implementation of the functions I needed (attached below).
Has anyone else done this? Should I polish it up and offer it for inclusion in Data?
I have a Trie implementation with a different, and even simpler, interface. The only operation is 'match' for search/insertion, and it does not store values at the nodes (although the latter restriction could be easily lifted). Regards, Malcolm
On Fri, 2005-02-11 at 11:28 +0000, Keith Wansbrough wrote:
Hi... I was writing some code yesterday to walk over a directory tree, and needed a Trie. Not seeing one around, I wrote a basic implementation of the functions I needed (attached below).
Has anyone else done this? Should I polish it up and offer it for inclusion in Data?
Dr. Ralf Hinze has an implementation of Tries too: http://www.informatik.uni-bonn.de/~ralf/software/Library/Trie.html I believe (but cannot now find the reference) that Ralf has licenced this code under the GPL (at least he allowed me to use it under the GPL). You'd want to check with him if you want a different license. I also have a version derived from Ralf's version for "MultiTries" ie like a bag rather than a set. http://cvs.sourceforge.net/viewcvs.py/haide/haide/src/utils/MultiTrie.lhs?rev=1.2&view=markup There's also a few QuickCheck tests for that module. Duncan
G'day all.
Quoting Keith Wansbrough
Hi... I was writing some code yesterday to walk over a directory tree, and needed a Trie. Not seeing one around, I wrote a basic implementation of the functions I needed (attached below).
Has anyone else done this? Should I polish it up and offer it for inclusion in Data?
Lots of people have. :-) Here's mine, for the record: http://cvs.sourceforge.net/viewcvs.py/hfl/hfl/edison/Assoc/TernaryTrie.hs?rev=1.18&view=auto Cheers, Andrew Bromage
Has anyone else done this? Should I polish it up and offer it for inclusion in Data?
Lots of people have. :-)
Here's mine, for the record:
OK, thanks all... I will see if I can pull them all together into something sensible for a Data.Trie proposal. Watch this space! --KW 8-)
On Mon, 2005-02-14 at 14:10 +0000, Keith Wansbrough wrote:
Has anyone else done this? Should I polish it up and offer it for inclusion in Data?
Lots of people have. :-)
Here's mine, for the record:
OK, thanks all... I will see if I can pull them all together into something sensible for a Data.Trie proposal. Watch this space!
Great! Now that we've got Data.IntMap which provides the Data.Map interface but specialised for Int keys (and with a fast implementation based on a different data structure), might it also be a good idea to do Data.StringMap and implement it in terms of Data.Trie Char? Am I right in thinking that Tries would usually be a faster finite map data structure than ordinary Data.Map balanced binary trees? Duncan
On Mon, Feb 14, 2005 at 04:03:59PM +0000, Duncan Coutts wrote:
On Mon, 2005-02-14 at 14:10 +0000, Keith Wansbrough wrote:
Has anyone else done this? Should I polish it up and offer it for inclusion in Data?
Lots of people have. :-)
Here's mine, for the record:
OK, thanks all... I will see if I can pull them all together into something sensible for a Data.Trie proposal. Watch this space!
Great!
Now that we've got Data.IntMap which provides the Data.Map interface but specialised for Int keys (and with a fast implementation based on a different data structure), might it also be a good idea to do Data.StringMap and implement it in terms of Data.Trie Char?
Am I right in thinking that Tries would usually be a faster finite map data structure than ordinary Data.Map balanced binary trees? What we really need is for someone to implement this :) http://research.microsoft.com/Users/simonpj/papers/assoc-types/index.htm
Then we can have a single Data.Map which uses Tries for list keys, IntMap for integral types, and so forth. John -- John Meacham - ⑆repetae.net⑆john⑈
I created a ticket for this, in case someone wants to pick up the task.
(Maybe myself, if I get to allocate some time for this)
http://hackage.haskell.org/trac/ghc/ticket/721
Cheers,
JP.
On 2/14/05, Keith Wansbrough
Has anyone else done this? Should I polish it up and offer it for inclusion in Data?
Lots of people have. :-)
Here's mine, for the record:
OK, thanks all... I will see if I can pull them all together into something sensible for a Data.Trie proposal. Watch this space!
--KW 8-)
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
participants (7)
-
ajb＠spamcop.net -
Duncan Coutts -
Jean-Philippe Bernardy -
John Meacham -
Keith Wansbrough -
Malcolm Wallace -
Tomasz Zielonka