2010/4/9 Heinrich Apfelmus <apfel...@quantentunnel.de>:
> 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 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)
>>
>> [...]
>>
>> 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
