[Haskell-cafe] Re: Suitable structure to represents lots of similar lists

[Heinrich Apfelmus]

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