On Wed, 2002-08-21 at 16:52, Hal Daume III wrote:
I would consider using a prefix trie. Unfortunately, such a structure is not built in to Haskell.
Thanks for this! It seems that this kind of data structure is what I am looking for. [begin aside] It seems a pity that one needs to give the data type a special name in order for it to be recursive. What I mean, is that other types can be expressed using built in manipulators, eg [(Int,[Char])] Of course you can use "data" to create specialized types which are essentially the same in structure, but earmarked for specialized use, but there is always the "raw" type to use as a default... But the same is not true (so it seems) for recursive types. Ie, it would be nice to represent what you call "PreTrie" as a raw type. Imagine you used the '*' symbol to mean "recursively refer to yourself", then you could write [(a, (Bool, *))] to be the "raw" version of PreTrie. This would mean you also did not need to worry about using "helper" functions like insert' and elem'. Anyway, that's just a few thoughts I've had --- perhaps they are naive? After all, I am fairly new to Haskell :-) [end aside]
A naive implementation would be something like (I haven't tested/compiled this code, so there are 'bugs'...consider it 'psuedo-haskell'):
I've taken your code and fixed the 'bugs' (I think). I've got a few questions. Here's the fixed version, along with my questions: data PreTrie a = PreTrie [(a, (Bool, PreTrie a))] -- (element, is-element-in-trie, children) Why did you call it "PreTrie" and not just "Trie"? Any particular reason? empty :: PreTrie a empty = PreTrie [] insert :: Eq a => PreTrie a -> [a] -> PreTrie a insert (PreTrie l) a = PreTrie (insert' l a) insert' [] [x] = [(x, (True, empty))] insert' [] (x:xs) = [(x, (False, insert empty xs))] insert' ((a,(b,c)):ls) [x] | a == x = (a,(True,c)) : ls | otherwise = (a,(b,c)) : insert' ls [x] insert' ((a,(b,c)):ls) (x:xs) | a == x = (a,(b,insert c xs)) : ls | otherwise = (a,(b,c)) : insert' ls (x:xs) varElem :: Eq a => PreTrie a -> [a] -> Bool varElem (PreTrie l) a = varElem' l a Using just "elem" as you had before, caused hugs to give me this error: Reading file "PreTrie.hs": ERROR PreTrie.hs:23 - Definition of variable "elem" clashes with import any idea why? varElem' [] _ = False varElem' ((a,(b,c)):ls) [x] | a == x = b | otherwise = varElem' ls [x] varElem' ((a,(b,c)):ls) (x:xs) | a == x = varElem c xs | otherwise = varElem' ls (x:xs) When I wanted to test this stuff in hugs, I had to do things like: Main> varElem (insert (insert (insert empty "a") "b") "ab") "b" True The way I would do things in an imperative language would be something like: x = insert empty "a" x = insert x "b" x = insert x "ab" ... varElem x "b" Now obviously I can't do this, but is there some different technique for building up a data structure like this, or is it just a case of me getting used to long lines and lots of brackets? One more thing... when I did: Main> insert (insert (insert empty "a") "b") "ab" ERROR - Cannot find "show" function for: *** Expression : insert (insert (insert empty "a") "b") "ab" *** Of type : PreTrie Char I tried to define show :: (PreTrie a) -> String show (PreTrie l) = show l but got ERROR PreTrie.hs:35 - Definition of variable "show" clashes with import Am I on the right track? Thanks for your help! Cheers, Mark.