[Haskell-cafe] Type issues for a foldable trie in Haskell

[Brad Larsen]

Hello there,

I have written a trie in Haskell generalized to Eq a => [a] rather than  
simply String.  I want to make this type an instance of Foldable, but I've  
run into a type dilemma.  My datatypes look like this:

data TrieElem a = Elem a | Start | End
   deriving (Read, Show, Eq, Ord)

data Trie a = Trie {label :: TrieElem a
                    ,children :: [Trie a]}
   deriving (Read, Show, Eq, Ord)

The signature of Data.Foldable.foldr is (Data.Foldable.Foldable t) => (a  
-> b -> b) -> b -> t a -> b.  However, I want the functions in Foldable to  
operate on the _list type_ that Trie stores rather than the _elements_ of  
that list type---Trie a stores lists of type a.  For example, a Trie  
storing strings would have type Trie Char, and I want Trie Char to be  
Foldable, but where the functions operate on String rather than Char.

So, with the datatype definitions of Trie and TrieElem as they are above,  
to define a fold function that operates the way I want would have  
signature ([a] -> b -> b) -> b -> Trie a -> b, which is no good for making  
Trie a an instance of Foldable.

Hopefully this doesn't just seem like rambling :-).  How might I rewrite  
my datatypes to do what I want, preferably without using ghc extensions?   
Thanks!

Brad Larsen