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

Edward Kmett ekmett at gmail.com
Wed Apr 7 19:13:14 EDT 2010


I've been meaning to generalize Data.Rope in my rope library to use Vector
rather than ByteString.

Ultimately it looks like a FingerTree of Vector's using length as the
monoid.

The vectors can be sliced cheaply and the fingertree as a whole supports
cheap splicing.

-Edward Kmett

On Wed, Apr 7, 2010 at 6:22 PM, Dan Piponi <dpiponi at gmail.com> 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.)
> --
> Dan
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100407/28ab59c1/attachment.html


More information about the Haskell-Cafe mailing list