[Haskell-cafe] I confused myself with generics, and now I confused ghc too

[José Pedro Magalhães]

Hi Ari,

I won't really try to answer your question, but I'll give you the code for
gzipWithQ written by Alexey Rodriguez Yakushev some years ago for his
comparison on generic programming libraries. The original darcs repo no
longer exists, but here is the file which I think is relevant for you:

> {-# OPTIONS_GHC -fglasgow-exts #-}
> > {-# OPTIONS_GHC -fallow-undecidable-instances #-}
> > {-# OPTIONS_GHC -fallow-overlapping-instances #-}
>
> > module Traversals where
>
> > import Data.Generics.SYB.WithClass.Basics
> > import BinTreeDatatype
> > import BinTreeReps
>
> These traversals were copied (and adapted) from CtxSchemes.hs.
> That file is distributed in
>
> < http://homepages.cwi.nl/~ralf/syb3/code.html
>
> The adaptations are necessary so that it works with SYB3 distributed in:
>
> < darcs get http://happs.org/HAppS/syb-with-class
>
> > -- | A type constructor for accumulation
> > newtype A a c d = A { unA :: a -> (a, c d) }
>
> > gfoldlAccum :: Data ctx d
> >             => Proxy ctx
> >             -> (forall d r. Data ctx d => a -> c (d -> r) -> d -> (a, c
> r))
> >             -> (forall g. a -> g -> (a, c g))
> >             -> a -> d -> (a, c d)
> >
> > gfoldlAccum ctx k z a d = unA (gfoldl ctx k' z' d) a
> >  where
> >   k' c y = A (\a -> let (a', c') = unA c a in k a' c' y)
> >   z' f   = A (\a -> z a f)
>
> > -- | gmapQr with accumulation
> > gmapAccumQr :: Data ctx d
> >             => Proxy ctx
> >             -> (r' -> r -> r)
> >             -> r
> >             -> (forall d. Data ctx d => a -> d -> (a,r'))
> >             -> a -> d -> (a, r)
> > gmapAccumQr ctx o r f a d = let (a',l) = gfoldlAccum ctx k z a d
> >                             in (a',unQr l r)
> >  where
> >   k a (Qr c) d = let (a',r') = f a d
> >                   in (a', Qr (\r -> c (r' `o` r)))
> >   z a _ = (a, Qr id)
>
>
> > -- | gmapQ with accumulation
> > gmapAccumQ :: Data ctx d
> >            => Proxy ctx
> >            -> (forall d. Data ctx d => a -> d -> (a,q))
> >            -> a -> d -> (a, [q])
> > gmapAccumQ ctx f = gmapAccumQr ctx (:) [] f
>
>
> Adapted from the source code of SYB 1&2 to work with syb3
>
> > gzipWithQ :: forall ctx r . Proxy ctx -> GenericQ ctx (GenericQ ctx r) ->
> GenericQ ctx (GenericQ ctx [r])
> > gzipWithQ ctx f x y = case gmapAccumQ ctx perkid funs y of
> >                    ([], r) -> r
> >                    _       -> error "gzipWithQ"
> >  where
> >   perkid a d = (tail a, unGQ (head a) d)
> >   funs :: [GenericQ' ctx r]
> >   funs = gmapQ ctx (\k -> GQ (f k)) x
> > newtype GenericQ' ctx r = GQ { unGQ :: GenericQ ctx r }
>
> Adapted from CtxSchemes.hs
>
> > everything :: Proxy ctx -> (r -> r -> r) -> GenericQ ctx r -> GenericQ
> ctx r
> > everything ctx k f x
> >   = foldl k (f x) (gmapQ ctx (everything ctx k f) x)
>
> > everywhere :: Proxy ctx -> GenericT ctx -> GenericT ctx
> > everywhere ctx f
> >   = f . gmapT ctx (everywhere ctx f)
>

Let me know if this doesn't work, or if you need something else.


Cheers,
Pedro

On Mon, Jul 18, 2011 at 15:42, Ari Rahikkala <ari.rahikkala at gmail.com>wrote:

> I want to implement generic comparison on top of syb-with-class, and
> based on looking at syb, it seems I could base it on something like
> gzipWithQ from syb's Data.Generics.Twins. However, there's no
> Data.Generics.SYB.WithClass.Twins. So I set out to see if I can write
> one myself (well, one with just enough stuff to support gzipWithQ
> anyway) Here's what I've got so far: http://hpaste.org/49168
>
> The problem is that GHCi seems to be somewhat confused, or at least
> confusing, about the type of gzipWithQ here. When I ask with :t, it
> reports the type as:
>
> gzipWithQ
>  :: (Data ctx a2, Data ctx a3, Data ctx a) =>
>     Proxy ctx
>     -> (forall a0.
>         Data ctx a0 =>
>         a0 -> forall a1. Data ctx a1 => a1 -> r)
>     -> a2
>     -> a3
>     -> [r]
>
> If I actually replace gzipWithQ's annotated type with this, GHCi will
> reject the program. And in any case with GenericQ being defined as
> "type GenericQ ctx r = Data ctx a => a -> r", isn't this closer to
> gzipWithQ's type with the type synonyms expanded?
>
> gzipWithQ :: forall ctx a r.
>             Data ctx a =>
>             Proxy ctx
>          -> (Data ctx a0 => a0 -> (Data ctx a1 => a1 -> r))
>          -> (Data ctx a2 => a2 -> (Data ctx a3 => a3 -> [r]))
>
> (GHCi accepts this as gzipWithQ's type so I assume it's the same one.
> I assume those class constraints after the => come with implicit
> foralls? Because it seems to mean the same thing if I put foralls in
> there)
>
> I have no idea how to even start figuring out how to make gzipWithQ
> and its type work. I only got this far by copying code from
> Data.Generics.Twins and passing down the proxy parameter and/or
> context type parameter (is it even possible for this approach to
> work?). What I can tell is that GHCi will still change the type like
> that even if gzipWithQ = undefined, so I'll have to change the type
> and not just the body of the function. Is this the kind of thing that
> all those newtypes in Data.Generics.Twins are for? Should I read up on
> type theory?
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110719/aa60a452/attachment.htm>