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

Eugene Kirpichov ekirpichov at gmail.com
Fri Apr 9 04:46:26 EDT 2010


2010/4/9 Heinrich Apfelmus <apfelmus at 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 xs at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
Eugene Kirpichov
Senior Developer, JetBrains


More information about the Haskell-Cafe mailing list