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

[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 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.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com