Rep: Add default implementation built on Generics

[bgamari]

Thanks due to @sjoerdvisscher for the seed of the implementation (see #8).

[bgamari]

Note that this depends upon https://github.com/ekmett/distributive/pull/8

[bgamari]

Fixed. The remaining Travis issue appears to be unrelated.

[bgamari]

ping.

[RyanGlScott]

I'd like to revive this PR from the dead, if possible.

Much of the functionality needed to implement this is now in adjunctions. We have Representable instances for all the relevant GHC.Generics datatypes as of 12812ea8d878bb871ca5de0863046d4b76c67768. The only thing we don't have is a generic default implementation.

I would charge ahead and just merge this were @treeowl's comment in https://github.com/ekmett/adjunctions/pull/13#issuecomment-263746804 not giving me pause. As he noted, this implementation will cause the typechecker to choke if it tries to generically derive a Representable instance for an infinite stream type. That is, this code (as of adjunctions HEAD):

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}

import           Data.Functor.Rep
import qualified GHC.Generics as Gen
import           GHC.Generics hiding (Rep)

data Stream a = a :> Stream a
  deriving (Functor, Generic1)

instance Representable Stream where
  type Rep Stream = Rep (Gen.Rep1 Stream)
  tabulate = to1 . tabulate
  index = index . from1

will fail to compile with what is essentially an infinite typechecker loop (thankfully caught early):

Foo.hs:15:20: error:
    • Reduction stack overflow; size = 201
      When simplifying the following type:
        Rep
          (M1
             S
             ('MetaSel
                'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy)
             Par1)
      Use -freduction-depth=0 to disable this check
      (any upper bound you could choose might fail unpredictably with
       minor updates to GHC, so disabling the check is recommended if
       you're sure that type checking should terminate)
    • In the second argument of ‘(.)’, namely ‘tabulate’
      In the expression: to1 . tabulate
      In an equation for ‘tabulate’: tabulate = to1 . tabulate

This is because the Rep type for Stream is Either () (Either () (Either () ...)), an infinity type which triggers a stack overflow before GHC can finish processing it.

Is there a way to work around this? Should we figure out a way to disallow these sorts of datatypes in the default implementation? Something else?

[treeowl]

Yes, the workaround is to wrap up Par and Rec representations in newtypes. Or about that.

On Jan 4, 2017 6:04 PM, "Ryan Scott" notifications@github.com wrote:

I'd like to revive this PR from the dead, if possible.

Much of the functionality needed to implement this is now in adjunctions. We have Representable instances for all the relevant GHC.Generics datatypes as of 12812ea https://github.com/ekmett/adjunctions/commit/12812ea8d878bb871ca5de0863046d4b76c67768. The only thing we don't have is a generic default implementation.

I would charge ahead and just merge this were @treeowl https://github.com/treeowl's comment in #13 (comment) https://github.com/ekmett/adjunctions/pull/13#issuecomment-263746804 not giving me pause. As he noted, this implementation will cause the typechecker to choke if it tries to generically derive a Representable instance for an infinite stream type. That is, this code (as of adjunctions HEAD):

{-# LANGUAGE DeriveFunctor #-} {-# LANGUAGE DeriveGeneric #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE UndecidableInstances #-} import Data.Functor.Repimport qualified GHC.Generics as Genimport GHC.Generics hiding (Rep) data Stream a = a :> Stream a deriving (Functor, Generic1) instance Representable Stream where type Rep Stream = Rep (Gen.Rep1 Stream) tabulate = to1 . tabulate index = index . from1

will fail to compile with what is essentially an infinite typechecker loop (thankfully caught early):

Foo.hs:15:20: error: • Reduction stack overflow; size = 201 When simplifying the following type: Rep (M1 S ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1) Use -freduction-depth=0 to disable this check (any upper bound you could choose might fail unpredictably with minor updates to GHC, so disabling the check is recommended if you're sure that type checking should terminate) • In the second argument of ‘(.)’, namely ‘tabulate’ In the expression: to1 . tabulate In an equation for ‘tabulate’: tabulate = to1 . tabulate

This is because the Rep type for Stream is Either () (Either () (Either () ...)), an infinity type which triggers a stack overflow before GHC can finish processing it.

Is there a way to work around this? Should we figure out a way to disallow these sorts of datatypes in the default implementation? Something else?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/ekmett/adjunctions/pull/12#issuecomment-270513233, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_db3ZBLZXignaBqKq2Iq0o6jD1f1ks5rPCWBgaJpZM4C9P8l .

[RyanGlScott]

Yes, the workaround is to wrap up Par and Rec representations in newtypes.

I don't follow. Do you have code that demonstrates how this works?

[treeowl]

Yeah, glguy showed me how. I guess Par isn't actually an issue. If you have

type Rep (Rec f) = Rep f

Then you loop. But you can break that with a newtype:

newtype Wrap f = Wrap (Rep f)

Then

type Rep (Rec f) = Wrap f

will not loop.

Or approximately that.

On Jan 4, 2017 6:37 PM, "Ryan Scott" notifications@github.com wrote:

Yes, the workaround is to wrap up Par and Rec representations in newtypes.

I don't follow. Do you have code that demonstrates how this works?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/ekmett/adjunctions/pull/12#issuecomment-270519393, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_U6fTH6OCNjREkNuuUDA8xkTfR_fks5rPC1BgaJpZM4C9P8l .

[treeowl]

More concretely:

newtype Wrap f = Wrap {unwrap :: Rep f}
instance (Representable f, Distributive (Gen.Rec1 f)) => Representable (Gen.Rec1 f) where
  type Rep (Gen.Rec1 f) = Wrap f
  tabulate f = Gen.Rec1 $ tabulate f
  index (Gen.Rec1 x) i = index x i

So now, GHC will reduce Rep (Gen.Rec1 f) to Wrap f, and be done, rather than continuing to reduce Rep f.

[treeowl]

Another option is to use a data family instead of a type family. I don't know the tradeoffs exactly.

On Jan 4, 2017 7:00 PM, "David Feuer" david.feuer@gmail.com wrote:

Yeah, glguy showed me how. I guess Par isn't actually an issue. If you have

type Rep (Rec f) = Rep f

Then you loop. But you can break that with a newtype:

newtype Wrap f = Wrap (Rep f)

Then

type Rep (Rec f) = Wrap f

will not loop.

Or approximately that.

On Jan 4, 2017 6:37 PM, "Ryan Scott" notifications@github.com wrote:

Yes, the workaround is to wrap up Par and Rec representations in newtypes.

I don't follow. Do you have code that demonstrates how this works?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/ekmett/adjunctions/pull/12#issuecomment-270519393, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_U6fTH6OCNjREkNuuUDA8xkTfR_fks5rPC1BgaJpZM4C9P8l .

[treeowl]

Er.... A separate GRepresentable class with a data family, that is.

On Jan 4, 2017 7:50 PM, "David Feuer" david.feuer@gmail.com wrote:

Another option is to use a data family instead of a type family. I don't know the tradeoffs exactly.

On Jan 4, 2017 7:00 PM, "David Feuer" david.feuer@gmail.com wrote:

Yeah, glguy showed me how. I guess Par isn't actually an issue. If you have

type Rep (Rec f) = Rep f

Then you loop. But you can break that with a newtype:

newtype Wrap f = Wrap (Rep f)

Then

type Rep (Rec f) = Wrap f

will not loop.

Or approximately that.

On Jan 4, 2017 6:37 PM, "Ryan Scott" notifications@github.com wrote:

Yes, the workaround is to wrap up Par and Rec representations in newtypes.

I don't follow. Do you have code that demonstrates how this works?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/ekmett/adjunctions/pull/12#issuecomment-270519393, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_U6fTH6OCNjREkNuuUDA8xkTfR_fks5rPC1BgaJpZM4C9P8l .

[treeowl]

Sorry for so many comments in a row! It may be worth seeing whether the type family approach or the data family approach makes the type checker performance better for large sums and products.

[RyanGlScott]

I went with the Wrap approach in #35, which has been merged.