Jon Harrop a écrit :
> So tries let us associate sequences with values. What data structure lets us 
> associate trees with values?
>
> I ask because I am interested in replacing hash consing of expressions with a 
> purely functional equivalent so I need a way to map expressions onto 
> expressions.
>
> The only idea I've come up with so far is to fold over the tree to make a 
> sequence and use that as the key into a trie but it seems a bit naff...
>
>   
I had the same pb and the same idea about fold ... I attached my code 
which has a lot of missing functions like removal and
very special function I needed (search_sub, sub_search, ...). It does a 
fold of the tree, but via a decomposition function, so you can choose in 
which order
you scan the son of each node.

This idea is not so naff. The map library has a complexity in O(N ln(S)) 
where N is the size of the key and S is the number of
item in the table. My current implementation is in O(N P) where P is the 
number of types of edges (that is the sum of the arities of all 
constructors).
It could be improved in O(N ln(P)) ... but I had no time.


Cheers,
Christophe