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

2010/4/8 Eugene Kirpichov :

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 extract :: Transformed a -> a extract (Unchanged a) = a extract (Changed a') = a'

-- If the first argument returns Nothing, that means 'identity' Whoops, this is an artifact of my brief thought to use Maybe instead of Transformed...

mapShared :: (a -> Transformed a) -> List a -> List a mapShared f xs = extract (mapShared' f xs)

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)

filterShared :: (a -> Bool) -> List a -> List a filterShared p xs = original xs (filterShared' p xs)

filterShared' :: (a -> Bool) -> List a -> Transformed (List a) filterShared' p xs@Nil = Unchanged xs filterShared' p xs@(Leaf x) = if p x then Unchanged xs else Changed Nil filterShared' p xs@(Cat ys zs) = cat xs (filterShared' p ys) (filterShared' p zs)

Perhaps this can be made into a monad or something like that, but I am not sure... Perhaps rebalancing (or generally using a finger tree) would also do well.

So, looks like we preserve whole 'subtrees' shared if they were not 'changed' by map or filter.

2010/4/8 Alberto G. Corona :

...

Id doesn´t have to create a copy of the original object  ( I infer this from referential transparency) so the new list must store the same original reference. Any pure structure would conserve references  after id. filter as far as I know. Am I wrong?

2010/4/8 Dan Piponi

...

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.) -- Dan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Senior Developer, JetBrains

-- Eugene Kirpichov Senior Developer, JetBrains