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

[Eugene Kirpichov]

2010/4/8 Eugene Kirpichov <ekirpichov at gmail.com>:
> 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)
Aargh. I meant:
filterShared p xs = extract (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
>



-- 
Eugene Kirpichov
Senior Developer, JetBrains