More suitable data structure needed

[Dr Mark H Phillips]

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.