Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths and the question of how it may be extended to the wider class of purely functional sequences based on trees.
The problem is the following: You want to test for almost certain structural equality in O(1) time by means of strong hashing. If the hash function is structurally recursive, i.e. hash (x:xs) = mix x (hash xs), then you can transparently cache hash values on lists and update them in O(1) time when an element is consed onto an existing list. Most algorithms for hashing lists are structurally recursive, so this approach is eminently usable in practice.
But suppose instead of singly-linked lists you have tree-based sequences that support concatenating two sequences of length O(n) in O(log n) time. For the hash caching to work here, the hash mixing function must be associative in order to respect the degrees of freedom a tree has in representing the same linear sequence. The mixer should take the hash values of the subtrees and calculate the hash value of the whole tree.
This is where I was six months ago when I spent a day mulling over and researching this problem. It seems to have received no attention in the literature on data structures. I did come across the Tillich-Zemor hashing algorithm from cryptography. It relies on 2x2 matrix multiplication (which is associative) where bits 0 and 1 correspond to the two generators of a subalgebra with entries in a Galois field.
My question is, what have I missed? There must be papers of relevance in both the literature on cryptography and data structures that I failed to find in my search. Any comments on this problem and possible venues to explore would be greatly appreciated.
Edit: I am interested in this question on both the soft and cryptographically strong ends of the spectrum. On the softer side it can be used for hash tables where collisions should be avoided but aren't catastrophic. On the stronger side it can be used for equality testing.