I don't know if they're at all suitable for your purposes, but you should look (at least for inspiration) at both vinyl and dependent-map.

Thanks David, vinyl is a record 'solution', not a set-of-records repository Really there's now too many bewildering choices for records; representing the records is not the difficult part. dependent-map, and vault [Heinrich Apfelmus,thank you Sergei for the suggestion] seem to be (key, value) stores so I'm not seeing how I 'query'/filter the values (the whole records) if I don't already know the keys for those records. Contrast that with Data.Set [*], you could stream the contents to a list and filter. (Which would be horribly inefficient for my purposes.) [*] Data.Set seems to have been swallowed into the new collections library, which is not currently maintained :-( AntC