[Haskell-cafe] Re: Suitable structure to represents lots of similar lists
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.
Regards,
Heinrich Apfelmus
--
http://apfelmus.nfshost.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Suitable structure to represents lots of similar lists
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
[Haskell-cafe] Re: Suitable structure to represents lots of similar lists
Dan Piponi wrote: 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.) I'm not sure whether these general properties of your maps and filters can actually be exploited. The thing is that you still have to touch every element anyway, so you can as well allocate a new cons cell and garbage collect the old one while you're at it. But if you can skip large contiguous parts of the lists, then sharing may be worth thinking about. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
