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

[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'
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 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)

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 at 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 <agocorona at gmail.com>:
> 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 <dpiponi at gmail.com>
>>
>> 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 at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>



-- 
Eugene Kirpichov
Senior Developer, JetBrains