[Haskell] Data.Generics.gzip3 anyone?

David Fox ddssff at gmail.com
Wed Jun 3 14:42:21 EDT 2009


Wait, its much funnier than that.  It wouldn't merge the three revisions
because they always differed in one field - the revision number!

On Tue, Jun 2, 2009 at 4:57 PM, David Fox <ddssff at gmail.com> wrote:

>
>
> On Tue, Jun 2, 2009 at 1:13 PM, David Fox <ddssff at gmail.com> wrote:
>
>> On Mon, Jun 1, 2009 at 3:40 PM, Ralf Laemmel <rlaemmel at gmail.com> wrote:
>>
>>> > Thank you!  What I have in mind is three way merging - you have two
>>> > revisions based on the same original value, and you need to decide
>>> whether
>>> > they can be merged automatically or they need to be merged by a user.
>>> You
>>> > only have a real conflict when both revisions differ from the original
>>> and
>>> > from each other.
>>>
>>> Here is the completed exercise.
>>> For comparison, the two args versions are shown up-front.
>>> There is gzipWithM3 needed for gzip3, and gzip3 itself.
>>> I also made it so that the top-level gzip functions have the
>>> appropriate polymorphism.
>>> Say same type for the args rather than independent polymorphism.
>>>
>>> {-# LANGUAGE RankNTypes #-}
>>>
>>> import Prelude hiding (GT)
>>> import Data.Generics
>>>
>>> -- As originally defined: Twin map for transformation
>>>
>>> gzipWithT2 :: GenericQ (GenericT) -> GenericQ (GenericT)
>>> gzipWithT2 f x y = case gmapAccumT perkid funs y of
>>>                    ([], c) -> c
>>>                    _       -> error "gzipWithT2"
>>>  where
>>>  perkid a d = (tail a, unGT (head a) d)
>>>  funs = gmapQ (\k -> GT (f k)) x
>>>
>>>
>>> -- As originally defined: Twin map for transformation
>>>
>>> gzipWithM2 :: Monad m => GenericQ (GenericM m) -> GenericQ (GenericM m)
>>> gzipWithM2 f x y = case gmapAccumM perkid funs y of
>>>                    ([], c) -> c
>>>                    _       -> error "gzipWithM"
>>>  where
>>>  perkid a d = (tail a, unGM (head a) d)
>>>  funs = gmapQ (\k -> GM (f k)) x
>>>
>>>
>>> -- As originally defined: generic zip
>>>
>>> gzip2 ::
>>>    (forall x. Data x => x -> x -> Maybe x)
>>>  -> (forall x. Data x => x -> x -> Maybe x)
>>>
>>> gzip2 f = gzip2' f'
>>>  where
>>>  f' :: GenericQ (GenericM Maybe)
>>>  f' x y = cast x >>= \x' -> f x' y
>>>  gzip2' :: GenericQ (GenericM Maybe) -> GenericQ (GenericM Maybe)
>>>  gzip2' f x y =
>>>    f x y
>>>    `orElse`
>>>    if toConstr x == toConstr y
>>>      then gzipWithM2 (gzip2' f) x y
>>>      else Nothing
>>>
>>>
>>> -- For three args now
>>>
>>> gzipWithT3 ::
>>>    GenericQ (GenericQ (GenericT))
>>>  -> GenericQ (GenericQ (GenericT))
>>> gzipWithT3 f x y z =
>>>    case gmapAccumT perkid funs z of
>>>      ([], c) -> c
>>>      _       -> error "gzipWithT3"
>>>  where
>>>  perkid a d = (tail a, unGT (head a) d)
>>>  funs = case gmapAccumQ perkid' funs' y of
>>>           ([], q) -> q
>>>           _       -> error "gzipWithT3"
>>>   where
>>>    perkid' a d = (tail a, unGQ (head a) d)
>>>    funs' = gmapQ (\k -> (GQ (\k' -> GT (f k k')))) x
>>>
>>> gzipWithM3 :: Monad m
>>>  => GenericQ (GenericQ (GenericM m))
>>>  -> GenericQ (GenericQ (GenericM m))
>>> gzipWithM3 f x y z =
>>>    case gmapAccumM perkid funs z of
>>>      ([], c) -> c
>>>      _       -> error "gzipWithM3"
>>>  where
>>>  perkid a d = (tail a, unGM (head a) d)
>>>   funs = case gmapAccumQ perkid' funs' y of
>>>           ([], q) -> q
>>>            _       -> error "gzipWithM3"
>>>    where
>>>    perkid' a d = (tail a, unGQ (head a) d)
>>>     funs' = gmapQ (\k -> (GQ (\k' -> GM (f k k')))) x
>>>
>>> gzip3 ::
>>>    (forall x. Data x => x -> x -> x -> Maybe x)
>>>  -> (forall x. Data x => x -> x -> x -> Maybe x)
>>>
>>> gzip3 f = gzip3' f'
>>>  where
>>>  f' :: GenericQ (GenericQ (GenericM Maybe))
>>>  f' x y z = cast x >>= \x' -> cast y >>= \y' -> f x' y' z
>>>  gzip3' ::
>>>       GenericQ (GenericQ (GenericM Maybe))
>>>    -> GenericQ (GenericQ (GenericM Maybe))
>>>  gzip3' f x y z =
>>>    f x y z
>>>    `orElse`
>>>    if and [toConstr x == toConstr y, toConstr y == toConstr z]
>>>      then gzipWithM3 (gzip3' f) x y z
>>>      else Nothing
>>>
>>
>> Ok, what I initially thought would work is not.  I tried to do the three
>> way merge as follows:
>>
>> combine3 :: (Data a) => a -> a -> a -> Maybe a
>> combine3 original left right =
>>     gzip3 f original left right
>>     where
>>       f :: forall a. (Data a) => a -> a -> a -> Maybe a
>>       f original left right
>>           | geq original left = Just right
>>           | geq original right = Just left
>>           | geq left right = Just left
>>           | otherwise = Nothing
>>
>> However, what happens is that we usually reach the otherwise clause when
>> processing the top level of the data structure, so you get nothing.  What
>> really needs to happen is that it traverses down into the data structure and
>> finds out that f is able to merge all the more primitive pieces of the data
>> structure, in which case it combines those merged parts to yield a merged
>> whole.  I'm not quite sure how to fit this operation into the generic
>> framework.
>>
>
> Oh, I got it.  I have to remove the "f x y z `orElse`" from the definition
> of gzip3.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell/attachments/20090603/dd4d5735/attachment.html


More information about the Haskell mailing list