Dan Piponi wrote:
I have a situation where I have a bunch of lists and I'll frequently be making new lists from the old ones by applying map and filter. The map will be applying a function that's effectively the identity on most elements of the list, and filter will be using a function that usually gives True. This means that there is potential for a large amount of sharing between these lists that could be exploited, something that ordinary lists would do badly. Does anyone have a recommendation for a pure functional data structure for this case?
(It reminds me a bit of my own antidiagonal type, but that's not well adapted to the highly dynamic situation I'm describing.)
I'm not sure whether these general properties of your maps and filters can actually be exploited. The thing is that you still have to "touch" every element anyway, so you can as well allocate a new cons cell and garbage collect the old one while you're at it. But if you can skip large contiguous parts of the lists, then sharing may be worth thinking about. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com