Generic tries (long)

[Jamie Brandon]

> Why not just use
>
>  class (Ord k, GMap map k) => OrderedGMap map k where

Most of the maps I will be implementing will respect the ordering that
would be derived by GHC, regardless of the actual Ord instance. There
is no way, in general, to derive a trie that respects an existing Ord
instance but I still want to expose the bytewise ordering in the trie.

We also already have

instance Ord k => OrderedGMap OrdGT k

where OrdGT use AVL trees.

> The term "association list" seems to be atomic, i.e. it's not a list of associations

Its not? 'Assocs' makes sense to me but I guess its best to copy the
terminology in Data.Map

> focus :: k -> map a -> (Maybe a, Maybe a -> map a)

I like focus, alter and merge. According to quickcheck my
serialisation code is now working so in a day or two I should be in a
position to   get some benchmarks set up. I would definitely prefer
the simpler interface if it can be persuaded to run reasonably
quickly. If not, I dont want to have a class definition that makes it
difficult to write efficient implentations. I would rather have an
ugly class and a nicer layer on top.

> The first thing to note is that what Jamie has posted is the proposed
> class methods *only*. It's not the complete user level map API.

Sorry, I'll update the api this evening with the user facing code. I
keep meaning to do it and then getting distracted by failed tests in
this damn bit munging code. (In my head lists run left to right and
machine words run right to left. This makes for some subtle bugs.)

For now I'm going to rename insert as insertWith and put insert in the
user api. Same for union, intersection etc