2010/4/9 Heinrich Apfelmus
Eugene Kirpichov wrote:
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 [...]
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 xs@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)
[...]
So, looks like we preserve whole 'subtrees' shared if they were not 'changed' by map or filter.
Yes, but do you actually gain in terms of space usage?
Oh! It appears to me that sometimes you do, namely when the list was heavily shared before applying map and filter. But if it's used ephemerally, you don't gain anything.
Yes, in an ephemeral scenario (i.e. compute sum (mapShared (mapShared (filterShared .... ( xs) )))) we seemingly don't gain anything at all, but it is precisely the scenario where we don't need sharing :) We do gain something if the program's working set of live objects includes many results of mapping and filtering the same list at once: then their sublists will be shared.
Regards, Heinrich Apfelmus
-- http://apfelmus.nfshost.com
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Eugene Kirpichov Senior Developer, JetBrains