Fixes most of #4989. I didn't add Persistent{Set,Map} since the only
persistent data structure is fun_treemap and its functionality is
currently too limited to build a trait out of.