I think Dan is talking about sharing the spine of the lists... How about representing the lists using something along the lines of:
data List a = Nil | Leaf a | Cat (List a) (List a) data Transformed a = Changed a | Unchanged a extract :: Transformed a -> a extract (Unchanged a) = a extract (Changed a') = a' -- If the first argument returns Nothing, that means 'identity' mapShared :: (a -> Transformed a) -> List a -> List a mapShared f xs = extract (mapShared' f xs) cat :: List a -> Transformed (List a) -> Transformed (List a) -> Transformed (List a) cat xs (Unchanged _) (Unchanged _) = Unchanged xs cat xs (Changed ys') (Unchanged zs) = Changed (Cat ys' zs) cat xs (Unchanged ys) (Changed zs') = Changed (Cat ys zs') cat xs (Changed ys') (Changed zs') = Changed (Cat ys' zs') mapShared' :: (a -> Transformed a) -> List a -> Transformed (List a) mapShared' f x...@nil = Unchanged xs mapShared' f xs@(Leaf a) = case f a of { Unchanged _ -> Unchanged xs ; Changed a' -> Changed (Leaf a') } mapShared' f xs@(Cat ys zs) = cat xs (mapShared' f ys) (mapShared' f zs) filterShared :: (a -> Bool) -> List a -> List a filterShared p xs = original xs (filterShared' p xs) filterShared' :: (a -> Bool) -> List a -> Transformed (List a) filterShared' p x...@nil = Unchanged xs filterShared' p xs@(Leaf x) = if p x then Unchanged xs else Changed Nil filterShared' p xs@(Cat ys zs) = cat xs (filterShared' p ys) (filterShared' p zs) Perhaps this can be made into a monad or something like that, but I am not sure... Perhaps rebalancing (or generally using a finger tree) would also do well. So, looks like we preserve whole 'subtrees' shared if they were not 'changed' by map or filter. 2010/4/8 Alberto G. Corona <agocor...@gmail.com>: > Id doesn´t have to create a copy of the original object ( I infer this from > referential transparency) so the new list must store the same original > reference. Any pure structure would conserve references after id. filter as > far as I know. Am I wrong? > > > 2010/4/8 Dan Piponi <dpip...@gmail.com> >> >> 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@haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > -- Eugene Kirpichov Senior Developer, JetBrains _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe