2010/4/8 Eugene Kirpichov <ekirpic...@gmail.com>: > 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' Whoops, this is an artifact of my brief thought to use Maybe instead of Transformed...
> 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 > -- Eugene Kirpichov Senior Developer, JetBrains _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe