Laws for GHC.Generics

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Laws for GHC.Generics

Gershom Bazerman
I had a bit of discussion today on how to handle generic instances for
abstract types.

It resolved to the following question, in a sense -- what are the laws
for the Generic typeclass?

Should require that `from` and `to` be an isomorphism of data types
(i.e. that `from . to` and `to . from` both be the identity) or should
we require only the weaker one-sided retract condition (i.e. that
`from . to` be the identity.). If the latter, is it better that `from`
be partial (which i  prefer) or that it quotient together "equivalent"
representations (i.e. representing a map as a `fromList` as
syb-generics do).

The documentation doesn't seem to provide clear guidance here, and it
might be worth discussing if some should be added.

Cheers,
Gershom
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Laws for GHC.Generics

David Feuer
Ryan Scott has argued that abstract types should not have Generic instances at all. I'll let him make those arguments himself, but I think I should mention that it's really hard to write instances that set up all the appropriate type-level meta-data. Some of it (like the extra-full package name) may only be doable with Template Haskell. Furthermore, some of the metadata types change from GHC version to version.

As for laws, I think you *probably* meant

to . from = id

That is, that you can convert a value to its generic representation and back and get the "same" value back.

I think that's likely sufficient for most purposes, but probably not all. At the very least, it's something people using your instance would need to be aware of. If either function is partial, you will be in a world of pain if you try to use something like generic serialization.

On Mar 20, 2017 4:53 PM, "Gershom B" <[hidden email]> wrote:
I had a bit of discussion today on how to handle generic instances for
abstract types.

It resolved to the following question, in a sense -- what are the laws
for the Generic typeclass?

Should require that `from` and `to` be an isomorphism of data types
(i.e. that `from . to` and `to . from` both be the identity) or should
we require only the weaker one-sided retract condition (i.e. that
`from . to` be the identity.). If the latter, is it better that `from`
be partial (which i  prefer) or that it quotient together "equivalent"
representations (i.e. representing a map as a `fromList` as
syb-generics do).

The documentation doesn't seem to provide clear guidance here, and it
might be worth discussing if some should be added.

Cheers,
Gershom
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Laws for GHC.Generics

Gershom Bazerman
Yes, you're right about `to . from`. I had it backwards.

Vis a vis:

> If either function is partial, you will be in a world of pain if
> you try to use something like generic serialization.

I'm not sure I understand. Deserialization is already partial if we're
considering the source as "all possible strings of bits" and the
target as a specific datatype? I don't see how having the conversion
from a generic be partial as well makes things any different?

(i.e. i think we're in a retract situation already)

-g



On Mon, Mar 20, 2017 at 5:16 PM, David Feuer <[hidden email]> wrote:

> Ryan Scott has argued that abstract types should not have Generic instances
> at all. I'll let him make those arguments himself, but I think I should
> mention that it's really hard to write instances that set up all the
> appropriate type-level meta-data. Some of it (like the extra-full package
> name) may only be doable with Template Haskell. Furthermore, some of the
> metadata types change from GHC version to version.
>
> As for laws, I think you *probably* meant
>
> to . from = id
>
> That is, that you can convert a value to its generic representation and back
> and get the "same" value back.
>
> I think that's likely sufficient for most purposes, but probably not all. At
> the very least, it's something people using your instance would need to be
> aware of. If either function is partial, you will be in a world of pain if
> you try to use something like generic serialization.
>
> On Mar 20, 2017 4:53 PM, "Gershom B" <[hidden email]> wrote:
>
> I had a bit of discussion today on how to handle generic instances for
> abstract types.
>
> It resolved to the following question, in a sense -- what are the laws
> for the Generic typeclass?
>
> Should require that `from` and `to` be an isomorphism of data types
> (i.e. that `from . to` and `to . from` both be the identity) or should
> we require only the weaker one-sided retract condition (i.e. that
> `from . to` be the identity.). If the latter, is it better that `from`
> be partial (which i  prefer) or that it quotient together "equivalent"
> representations (i.e. representing a map as a `fromList` as
> syb-generics do).
>
> The documentation doesn't seem to provide clear guidance here, and it
> might be worth discussing if some should be added.
>
> Cheers,
> Gershom
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Laws for GHC.Generics

David Feuer
Suppose we have

desGen :: DG f => ByteString -> Deserializer (f r)

We can then use

fmap to . desGen

to deserialize a value of a type with a Generic instance. But if `to` is partial, this doesn't produce a deserialization error; it makes the whole program blow up. So you're relying on your "generic" deserializer (the DG instance) to produce only values acceptable to `to`. It isn't actually generic at all!

On Mar 20, 2017 5:37 PM, "Gershom B" <[hidden email]> wrote:
Yes, you're right about `to . from`. I had it backwards.

Vis a vis:

> If either function is partial, you will be in a world of pain if
> you try to use something like generic serialization.

I'm not sure I understand. Deserialization is already partial if we're
considering the source as "all possible strings of bits" and the
target as a specific datatype? I don't see how having the conversion
from a generic be partial as well makes things any different?

(i.e. i think we're in a retract situation already)

-g



On Mon, Mar 20, 2017 at 5:16 PM, David Feuer <[hidden email]> wrote:
> Ryan Scott has argued that abstract types should not have Generic instances
> at all. I'll let him make those arguments himself, but I think I should
> mention that it's really hard to write instances that set up all the
> appropriate type-level meta-data. Some of it (like the extra-full package
> name) may only be doable with Template Haskell. Furthermore, some of the
> metadata types change from GHC version to version.
>
> As for laws, I think you *probably* meant
>
> to . from = id
>
> That is, that you can convert a value to its generic representation and back
> and get the "same" value back.
>
> I think that's likely sufficient for most purposes, but probably not all. At
> the very least, it's something people using your instance would need to be
> aware of. If either function is partial, you will be in a world of pain if
> you try to use something like generic serialization.
>
> On Mar 20, 2017 4:53 PM, "Gershom B" <[hidden email]> wrote:
>
> I had a bit of discussion today on how to handle generic instances for
> abstract types.
>
> It resolved to the following question, in a sense -- what are the laws
> for the Generic typeclass?
>
> Should require that `from` and `to` be an isomorphism of data types
> (i.e. that `from . to` and `to . from` both be the identity) or should
> we require only the weaker one-sided retract condition (i.e. that
> `from . to` be the identity.). If the latter, is it better that `from`
> be partial (which i  prefer) or that it quotient together "equivalent"
> representations (i.e. representing a map as a `fromList` as
> syb-generics do).
>
> The documentation doesn't seem to provide clear guidance here, and it
> might be worth discussing if some should be added.
>
> Cheers,
> Gershom
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Laws for GHC.Generics

Edward Kmett-2
In reply to this post by Gershom Bazerman
When implementing Data instances for abstract data types to avoid the horrible mess we used to get with opaque map types and the like, I've found it useful to use a "model" type internally, like modeling a Map as some kind of quotient of a list with a fake "constructor" for the function that wraps it.

https://github.com/haskell/containers/blob/master/Data/Map/Internal.hs#L483

In such cases we were able to avoid introducing any new undefined cases. I'd really personally prefer if such abstract generic instances could likewise avoid throwing around bottoms into the surrounding code. Letting folks generically change out keys in a map is actually quite useful, having the structure you rebuild randomly bottom out becaue you did so is a lot less so.

This would imply limiting yourself to just the `to . from = id` law for such abstract Generic instances (mutatis mutandis for Generic1).

This has the unfortunate property that you can now sometimes detect when you do choose to break a transformation into two passes, and from . to in the middle you get detectable differences from if you do it in one pass, but would allow you to define such things as pretending a map is a list of pairs, letting you walk in to the keys and the values.

If we thought a tiny bit harder about how to represent such pseudo-constructors we might be able to make it even safe for users to reason about when this is the only guarantee they get as opposed to normal. e.g. perhaps by representing it as a different M1 argument than C1 does (MetaCons) or extending MetaCons with an extra type level Bool indicating such 'abstract' use? This could almost just be done by the user detecting the lowercase first letter in the constructor name by introspecting on the symbol carried in the "virtual" MetaCons, but unfortunately Symbols are completely opaque as types right now, so guarding against such instances has to be done at the term rather than type level.

-Edward

On Mon, Mar 20, 2017 at 4:52 PM, Gershom B <[hidden email]> wrote:
I had a bit of discussion today on how to handle generic instances for
abstract types.

It resolved to the following question, in a sense -- what are the laws
for the Generic typeclass?

Should require that `from` and `to` be an isomorphism of data types
(i.e. that `from . to` and `to . from` both be the identity) or should
we require only the weaker one-sided retract condition (i.e. that
`from . to` be the identity.). If the latter, is it better that `from`
be partial (which i  prefer) or that it quotient together "equivalent"
representations (i.e. representing a map as a `fromList` as
syb-generics do).

The documentation doesn't seem to provide clear guidance here, and it
might be worth discussing if some should be added.

Cheers,
Gershom
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Loading...