[prev in list] [next in list] [prev in thread] [next in thread]
List: haskell-generics
Subject: Re: [Hs-Generics] pervasiveness of Rec in TH-derived
From: José_Pedro_Magalhães <jpm () cs ! uu ! nl>
Date: 2011-02-17 13:00:19
Message-ID: AANLkTinhPB38Q3mpKN8nMgz-FgpxCErga+3C7UYYZWi8 () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
Hi,
2011/2/16 Nicolas Frisby <nicolas.frisby@gmail.com>
> Thanks for the quick response!
>
> The Mappable class from Section 4.2 of the Fast and Easy! paper left
> me with the feeling that Rec and Var were useful. Has something else
> replaced that use in those examples or am I overestimating their
> usefulness?
>
There the Var is applied to a single type variable (let's assume it is the
last type variable of kind *). Then you can use this to write an fmap, which
is quite cool. Let me paste here the code adapted to work with the released
version:
import Generics.Instant
> import Generics.Instant.Instances
>
> class Mappable t a b where
> type Rebind t a b
> mapit :: (a -> b) -> t -> Rebind t a b
>
> instance Mappable U a b where
> type Rebind U a b = U
> mapit f U = U
>
> instance (Mappable t a b) => Mappable (C c t) a b where
> type Rebind (C c t) a b = C c (Rebind t a b)
> mapit f (C a) = C (mapit f a)
>
> instance (Mappable t a b, Mappable u a b) => Mappable (t :*: u) a b where
> type Rebind (t :*: u) a b = Rebind t a b :*: Rebind u a b
> mapit f (t :*: u) = mapit f t :*: mapit f u
>
> instance (Mappable t a b, Mappable u a b) => Mappable (t :+: u) a b where
> type Rebind (t :+: u) a b = Rebind t a b :+: Rebind u a b
> mapit f (L t) = L (mapit f t)
> mapit f (R u) = R (mapit f u)
>
> instance Mappable (Var a) a b where
> type Rebind (Var a) a b = Var b
> mapit f (Var a) = Var (f a)
>
> class Fun f where
> mapp :: (a -> b) -> f a -> f b
>
> instance Fun f => Mappable (Rec (f a)) a b where
> type Rebind (Rec (f a)) a b = Rec (f b)
> mapit f (Rec t) = Rec (mapp f t)
>
> generic_map :: (Representable (f a), Representable (f b),
> Mappable (Rep (f a)) a b,
> Rebind (Rep (f a)) a b ~ Rep (f b))
> => (a -> b) -> f a -> f b
> generic_map f x = to (mapit f (from x))
>
> instance Fun [] where mapp = generic_map
> instance Fun Maybe where mapp = generic_map
>
If you want to support datatypes with more type variables (like Either, for
instance), I think you need to add another representation type, e.g. Other,
which tags things that are not to be mapped over:
data Oth a = Oth a
>
> instance Representable (Either a b) where
> type Rep (Either a b) = (Oth a :+: Var b)
> from (Left a) = L (Oth a)
> from (Right a) = R (Var a)
> to (L (Oth a)) = Left a
> to (R (Var a)) = Right a
>
> instance Mappable (Oth a) b c where
> type Rebind (Oth a) b c = Oth a
> mapit f (Oth a) = Oth a
>
> instance Fun (Either a) where mapp = generic_map
>
What I haven't yet tried is an example with mutually recursive datatypes.
This relates to your next question...
>
> Would there be any harm in determining the mutually recursive
> datatypes and Rec-tagging exactly those fields that are part of the
> mutually recursive group? We might have some bitrotted TH code lying
> around that identifies the strongly connected types in a mutual
> recursive group of declarations. Please let me know if that's an
> attractive way forward for determining whether or not to insert the
> Rec.
>
So, for the code that is currently on Hackage, I don't think there would be
any harm in doing this; it would be great, actually. But I don't know how it
would affect the generic_map above... but, anyway, the generic_map above
wouldn't work with the current TH code, so something will have to change if
we want to incorporate generic_map.
Cheers,
Pedro
>
> 2011/2/16 José Pedro Magalhães <jpm@cs.uu.nl>:
> > Hi,
> >
> > On Wed, Feb 16, 2011 at 23:03, Nicolas Frisby <nicolas.frisby@gmail.com>
> > wrote:
> > >
> > > In instant-generics-0.2.1, the TH functions for deriving the Rep type
> > > instances insert the "Rec" type at every field. Is there a consequence
> > > to this?
> > >
> > > This behavior seems at odds with the paper; isn't Rec only meant as an
> > > indicator of recursive occurrences within the original data type?
> >
> > I think that is the current behavior, yes. I've given some thought to
> this
> > in the generic deriving paper [1]; in fact, tagging a recursive
> occurrence
> > with Var or Rec doesn't make much difference, since in the end it is just
> a
> > tag. You can't, for instance, define an fmap function by mapping over the
> > things tagged with Var, because you know nothing about the types of those
> > things.
> >
> > This doesn't mean they are entirely useless, though. In fact,
> > instant-generics makes use of this in the empty function [2]: on a sum,
> it
> > looks ahead to see if there are Rec's on the left or right, and proceeds
> to
> > the side that has no Rec's. This guarantees that a finite element will be
> > generated (if there is one). So, tagging only the occurrences of the
> > original type with Rec wouldn't be very helpful, since datatypes can be
> > mutually recursive.
> >
> > I think the best approach is to tag everything as Rec, except for
> parameters
> > and base types. That is what we do in UHC [1], if I recall correctly.
> >
> > And, as the comment says, the TH code for instant-generics should be
> updated
> > to generate Var tags too. I haven't gotten around to do that yet, but if
> > it's important for you I can have a look. Of course, patches are welcome
> too
> > [3].
> >
> >
> > Cheers,
> > Pedro
> >
> > [1] http://www.dreixel.net/research/pdf/gdmh.pdf
> > [2]
> >
> http://hackage.haskell.org/packages/archive/instant-generics/0.2.1/doc/html/Generics-Instant-Functions-Empty.html
>
> > [3]
> https://subversion.cs.uu.nl/repos/project.dgp-haskell.libraries/Instant/
> >
> > >
> > > Thanks.
> > >
> > > ---
> > >
> > > snippet from http://j.mp/gK8MOk ; repField is invoked for every field
> > > of every constructor by all of the relevant TH entry-points.
> > >
> > > repField :: (Name, [Name]) -> Type -> Q Type
> > > --repField d t | t == dataDeclToType d = conT ''I
> > > repField d t = conT ''Rec `appT` return t
> > >
> > > repField' :: (Name, [Name]) -> Name -> (Name, Strict, Type) -> Q Type
> > > --repField' d ns (_, _, t) | t == dataDeclToType d = conT ''I
> > > repField' (dt, vs) ns (f, _, t) = conT ''Rec `appT` return t
> > > -- Note: we should generate Var too, at some point
> > >
> > > _______________________________________________
> > > Generics mailing list
> > > Generics@haskell.org
> > > http://www.haskell.org/mailman/listinfo/generics
> >
> >
>
[Attachment #5 (text/html)]
Hi,<br><br><div class="gmail_quote">2011/2/16 Nicolas Frisby <span dir="ltr"><<a \
href="mailto:nicolas.frisby@gmail.com">nicolas.frisby@gmail.com</a>></span><br><blockquote \
class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, \
204, 204); padding-left: 1ex;"> Thanks for the quick response!<br>
<br>
The Mappable class from Section 4.2 of the Fast and Easy! paper left<br>
me with the feeling that Rec and Var were useful. Has something else<br>
replaced that use in those examples or am I overestimating their<br>
usefulness?<br></blockquote><div><br>There the Var is applied to a single type \
variable (let's assume it is the last type variable of kind *). Then you can use \
this to write an fmap, which is quite cool. Let me paste here the code adapted to \
work with the released version:<br> <br><blockquote style="margin: 0pt 0pt 0pt 0.8ex; \
border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex; font-family: courier \
new,monospace;" class="gmail_quote">import Generics.Instant<br>import \
Generics.Instant.Instances<br> <br>class Mappable t a b where<br> type Rebind t a \
b<br> mapit :: (a -> b) -> t -> Rebind t a b<br><br>instance Mappable U a b \
where<br> type Rebind U a b = U<br> mapit f U = U<br><br>instance (Mappable t a b) \
=> Mappable (C c t) a b where<br> type Rebind (C c t) a b = C c (Rebind t a \
b)<br> mapit f (C a) = C (mapit f a)<br><br>instance (Mappable t a b, Mappable u a \
b) => Mappable (t :*: u) a b where<br> type Rebind (t :*: u) a b = Rebind t a b \
:*: Rebind u a b<br> mapit f (t :*: u) = mapit f t :*: mapit f u<br><br>instance \
(Mappable t a b, Mappable u a b) => Mappable (t :+: u) a b where<br> type Rebind \
(t :+: u) a b = Rebind t a b :+: Rebind u a b<br> mapit f (L t) = L (mapit f t)<br> \
mapit f (R u) = R (mapit f u)<br><br>instance Mappable (Var a) a b where<br> type \
Rebind (Var a) a b = Var b<br> mapit f (Var a) = Var (f a)<br><br>class Fun f \
where<br> mapp :: (a -> b) -> f a -> f b<br><br> instance Fun f => \
Mappable (Rec (f a)) a b where<br> type Rebind (Rec (f a)) a b = Rec (f b)<br> \
mapit f (Rec t) = Rec (mapp f t)<br><br>generic_map :: (Representable (f a), \
Representable (f b),<br> Mappable (Rep (f a)) a b, <br> Rebind (Rep \
(f a)) a b ~ Rep (f b))<br> => (a -> b) -> f a -> f \
b<br>generic_map f x = to (mapit f (from x))<br><br>instance Fun [] where mapp = \
generic_map<br>instance Fun Maybe where mapp = generic_map<br> </blockquote><br>If \
you want to support datatypes with more type variables (like Either, for instance), I \
think you need to add another representation type, e.g. Other, which tags things that \
are not to be mapped over:<br> <br><blockquote style="margin: 0pt 0pt 0pt 0.8ex; \
border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex; font-family: courier \
new,monospace;" class="gmail_quote">data Oth a = Oth a<br><br>instance Representable \
(Either a b) where<br> type Rep (Either a b) = (Oth a :+: Var b)<br> from (Left a) \
= L (Oth a)<br> from (Right a) = R (Var a)<br> to (L (Oth a)) = Left a<br> to (R \
(Var a)) = Right a<br><br>instance Mappable (Oth a) b c where<br> type Rebind (Oth \
a) b c = Oth a<br> mapit f (Oth a) = Oth a<br><br>instance Fun (Either a) where mapp \
= generic_map<br></blockquote><br>What I haven't yet tried is an example with \
mutually recursive datatypes. This relates to your next question...<br> \
</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: \
1px solid rgb(204, 204, 204); padding-left: 1ex;"> <br>
Would there be any harm in determining the mutually recursive<br>
datatypes and Rec-tagging exactly those fields that are part of the<br>
mutually recursive group? We might have some bitrotted TH code lying<br>
around that identifies the strongly connected types in a mutual<br>
recursive group of declarations. Please let me know if that's an<br>
attractive way forward for determining whether or not to insert the<br>
Rec.<br></blockquote><div><br>So, for the code that is currently on Hackage, I \
don't think there would be any harm in doing this; it would be great, actually. \
But I don't know how it would affect the generic_map above... but, anyway, the \
generic_map above wouldn't work with the current TH code, so something will have \
to change if we want to incorporate generic_map.<br> <br><br>Cheers,<br>Pedro<br> \
</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: \
1px solid rgb(204, 204, 204); padding-left: 1ex;"> <br>
2011/2/16 José Pedro Magalhães <<a \
href="mailto:jpm@cs.uu.nl">jpm@cs.uu.nl</a>>:<br> <div><div></div><div \
class="h5">> Hi,<br> ><br>
> On Wed, Feb 16, 2011 at 23:03, Nicolas Frisby <<a \
href="mailto:nicolas.frisby@gmail.com">nicolas.frisby@gmail.com</a>><br> > \
wrote:<br> >><br>
>> In instant-generics-0.2.1, the TH functions for deriving the Rep type<br>
>> instances insert the "Rec" type at every field. Is there a \
consequence<br> >> to this?<br>
>><br>
>> This behavior seems at odds with the paper; isn't Rec only meant as \
an<br> >> indicator of recursive occurrences within the original data type?<br>
><br>
> I think that is the current behavior, yes. I've given some thought to \
this<br> > in the generic deriving paper [1]; in fact, tagging a recursive \
occurrence<br> > with Var or Rec doesn't make much difference, since in the \
end it is just a<br> > tag. You can't, for instance, define an fmap function \
by mapping over the<br> > things tagged with Var, because you know nothing about \
the types of those<br> > things.<br>
><br>
> This doesn't mean they are entirely useless, though. In fact,<br>
> instant-generics makes use of this in the empty function [2]: on a sum, it<br>
> looks ahead to see if there are Rec's on the left or right, and proceeds \
to<br> > the side that has no Rec's. This guarantees that a finite element \
will be<br> > generated (if there is one). So, tagging only the occurrences of \
the<br> > original type with Rec wouldn't be very helpful, since datatypes can \
be<br> > mutually recursive.<br>
><br>
> I think the best approach is to tag everything as Rec, except for parameters<br>
> and base types. That is what we do in UHC [1], if I recall correctly.<br>
><br>
> And, as the comment says, the TH code for instant-generics should be updated<br>
> to generate Var tags too. I haven't gotten around to do that yet, but if<br>
> it's important for you I can have a look. Of course, patches are welcome \
too<br> > [3].<br>
><br>
><br>
> Cheers,<br>
> Pedro<br>
><br>
> [1] <a href="http://www.dreixel.net/research/pdf/gdmh.pdf" \
target="_blank">http://www.dreixel.net/research/pdf/gdmh.pdf</a><br> > [2]<br>
> <a href="http://hackage.haskell.org/packages/archive/instant-generics/0.2.1/doc/html/Generics-Instant-Functions-Empty.html" \
target="_blank">http://hackage.haskell.org/packages/archive/instant-generics/0.2.1/doc/html/Generics-Instant-Functions-Empty.html</a><br>
> [3] <a href="https://subversion.cs.uu.nl/repos/project.dgp-haskell.libraries/Instant/" \
target="_blank">https://subversion.cs.uu.nl/repos/project.dgp-haskell.libraries/Instant/</a><br>
><br>
>><br>
>> Thanks.<br>
>><br>
>> ---<br>
>><br>
>> snippet from <a href="http://j.mp/gK8MOk" \
target="_blank">http://j.mp/gK8MOk</a> ; repField is invoked for every field<br> \
>> of every constructor by all of the relevant TH entry-points.<br> \
>><br> >> repField :: (Name, [Name]) -> Type -> Q Type<br>
>> --repField d t | t == dataDeclToType d = conT ''I<br>
>> repField d t = conT ''Rec `appT` return t<br>
>><br>
>> repField' :: (Name, [Name]) -> Name -> (Name, Strict, Type) -> \
Q Type<br> >> --repField' d ns (_, _, t) | t == dataDeclToType d = conT \
''I<br> >> repField' (dt, vs) ns (f, _, t) = conT ''Rec \
`appT` return t<br> >> -- Note: we should generate Var too, at some point<br>
>><br>
>> _______________________________________________<br>
>> Generics mailing list<br>
>> <a href="mailto:Generics@haskell.org">Generics@haskell.org</a><br>
>> <a href="http://www.haskell.org/mailman/listinfo/generics" \
target="_blank">http://www.haskell.org/mailman/listinfo/generics</a><br> ><br>
><br>
</div></div></blockquote></div><br>
_______________________________________________
Generics mailing list
Generics@haskell.org
http://www.haskell.org/mailman/listinfo/generics
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic