Data.Generics.gzip3 anyone?
Is there a Scrap Your Boilerplate guru out there who could whip up a three argument version of gzip for me?
On Mon, Jun 1, 2009 at 8:20 PM, David Fox <david@seereason.com> wrote:
Is there a Scrap Your Boilerplate guru out there who could whip up a three argument version of gzip for me?
This can be done of course (untested but type-checked code follows). Left wondering what the scenario might be :-) Ralf 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 -- 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
On Mon, Jun 1, 2009 at 12:20 PM, Ralf Laemmel <rlaemmel@gmail.com> wrote:
On Mon, Jun 1, 2009 at 8:20 PM, David Fox <david@seereason.com> wrote:
Is there a Scrap Your Boilerplate guru out there who could whip up a three argument version of gzip for me?
This can be done of course (untested but type-checked code follows). Left wondering what the scenario might be :-)
Ralf
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
-- 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
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. -david
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
On Mon, Jun 1, 2009 at 3:40 PM, Ralf Laemmel <rlaemmel@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
Oh, thank goodness! -david
Hello, Would there be interest in having this function added to the SYB library? Thanks, Pedro On Tue, Jun 2, 2009 at 00:40, Ralf Laemmel <rlaemmel@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 _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
I definitely think these functions should be added to syb. I certainly could not have written them myself without hours, perhaps days, of study. 2009/6/2 José Pedro Magalhães <jpm@cs.uu.nl>
Hello,
Would there be interest in having this function added to the SYB library?
Thanks, Pedro
On Tue, Jun 2, 2009 at 00:40, Ralf Laemmel <rlaemmel@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 _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On Mon, Jun 1, 2009 at 3:40 PM, Ralf Laemmel <rlaemmel@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.
On Tue, Jun 2, 2009 at 1:13 PM, David Fox <ddssff@gmail.com> wrote:
On Mon, Jun 1, 2009 at 3:40 PM, Ralf Laemmel <rlaemmel@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.
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@gmail.com> wrote:
On Tue, Jun 2, 2009 at 1:13 PM, David Fox <ddssff@gmail.com> wrote:
On Mon, Jun 1, 2009 at 3:40 PM, Ralf Laemmel <rlaemmel@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.
Ok, here is another piece of the three way merging puzzle. The gzip3 function can do three way merging when there are no conflicts that need to be resolved manually. When there are such conflicts we need a user interface which displays the common ancestor, the two alternative edits, and provides a place to input the merged result. For this we are using a generic programming interface to formlets . Formlets are members of class Applicative, so we can write a function to turn a value into a formlet using a gmapA function (this is syb-with-class generics): type GenericA f ctx = forall a. (Applicative f, Data ctx a) => a -> f a gmapA :: (Applicative f) => Proxy ctx -> GenericA f ctx -> GenericA f ctx gmapA ctx f = gfoldl ctx k pure where k c x = c <*> (f x) Then the formlet for a value is created using something like this: gmapA formletOfProxy (formletOfD dict) x For three way merging, though, we need to turn three values of the same type into a formlet, something like a gmap3A function: gmap3A formletOfProxy (formletOfD dict) ancestor variant1 variant2 Its this gmap3A function that I'm unable to create. I'm hoping someone out there will find this a piece of cake... On Mon, Jun 1, 2009 at 3:40 PM, Ralf Laemmel <rlaemmel@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
On Sat, Aug 8, 2009 at 4:05 PM, David Fox <ddssff@gmail.com> wrote:
Ok, here is another piece of the three way merging puzzle. The gzip3 function can do three way merging when there are no conflicts that need to be resolved manually. When there are such conflicts we need a user interface which displays the common ancestor, the two alternative edits, and provides a place to input the merged result. For this we are using a generic programming interface to formlets . Formlets are members of class Applicative, so we can write a function to turn a value into a formlet using a gmapA function (this is syb-with-class generics):
type GenericA f ctx = forall a. (Applicative f, Data ctx a) => a -> f a
gmapA :: (Applicative f) => Proxy ctx -> GenericA f ctx -> GenericA f ctx gmapA ctx f = gfoldl ctx k pure where k c x = c <*> (f x)
Then the formlet for a value is created using something like this:
gmapA formletOfProxy (formletOfD dict) x
For three way merging, though, we need to turn three values of the same type into a formlet, something like a gmap3A function:
gmap3A formletOfProxy (formletOfD dict) ancestor variant1 variant2
I guess this should be a more like this: gmap3A formletOfProxy (formletOf3WayMergeD dict) ancestor variant1 variant2 when converting a value of an arbitrary algebraic type, and formletOf3WayMerge would have custom implementations for various primitive and more specialized types.
Its this gmap3A function that I'm unable to create. I'm hoping someone out there will find this a piece of cake...
On Mon, Jun 1, 2009 at 3:40 PM, Ralf Laemmel <rlaemmel@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
participants (4)
-
David Fox -
David Fox -
José Pedro Magalhães -
Ralf Laemmel