This makes me a bit nervous. If I understand correctly, gplate in lens will not traverse any substructures nested inside other types, whereas the definition here will do so iff they have a Generic instance that is apparent at the call site. What happens if you have a polymorphic type that later gets instantiated?

GPlateInner is hidden and it will not be resolved before GPlated is resolved, whereas GPlated will not resolve until the type is known, so it looks fine to me.

Example:

λ> let f = toListOf gplate :: (a, b) -> [a]

<interactive>:16:18: error:
    • Overlapping instances for GPlated
                                  25 (GHC.Generics.K1 GHC.Generics.R b1) a1
        arising from a use of ‘gplate’
      Matching instances:
        two instances involving out-of-scope types
          instance Optics.Traversal.GPlateInner
                     (Optics.Internal.Optic.TypeLevel.HasRep (GHC.Generics.Rep b))
                     (1 GHC.TypeNats.<=? n)
                     (n GHC.TypeNats.- 1)
                     b
                     a =>
                   GPlated n (GHC.Generics.K1 i b) a
            -- Defined at src/Optics/Traversal.hs:535:3
          instance [overlapping] GPlated n (GHC.Generics.K1 i a) a
            -- Defined at src/Optics/Traversal.hs:530:30
      (The choice depends on the instantiation of ‘b1, a1’
       To pick the first instance above, use IncoherentInstances
       when compiling the other instance declarations)
    • In the first argument of ‘toListOf’, namely ‘gplate’
      In the expression: toListOf gplate :: (a, b) -> [a]
      In an equation for ‘f’: f = toListOf gplate :: (a, b) -> [a]

I guess your concern was that if this was permitted and then f was used e.g. with b ~ a, right?

Right, that's the kind of thing I was worried about. And the point is that we can't simplify GPlated n (K1 i b) a until we know that a is apart from b, which means we must have a concrete type for b, at which point we know whether it has a Generic instance... except if someone defines an orphan Generic instance later?

I haven't tested, but I think in the orphan case, one can have the "same" gplate call return different results because one has the Generic instance in scope and the other does not. Is that a deserved punishment for creating orphans?

Yeah, if there is no Generic instance for the type in question in scope when GPlated is resolved, gplate won't traverse it.

IMO documenting it should suffice, i.e. the note in gplate needs to be refined.

Yes, I'm okay with just documenting this.

Right, that's the kind of thing I was worried about. And the point is that we can't simplify GPlated n (K1 i b) a until we know that a is apart from b, which means we must have a concrete type for b, at which point we know whether it has a Generic instance... except if someone defines an orphan Generic instance later?

I haven't tested, but I think in the orphan case, one can have the "same" gplate call return different results because one has the Generic instance in scope and the other does not. Is that a deserved punishment for creating orphans?

What does "immediate" mean here?

That when it sees a, it won't try to traverse it further in search for another a within it (though I'm not sure if that's even possible). I'm not sure how to express that better 🤔

How about dropping "immediate", and adding a sentence along the lines of "If a occurs recursively in its own definition, only outermost occurrences of a within s will be traversed." For example:

>>> toListOf gplate "foo" :: [String]
["oo"]
>>> toListOf gplate ("foo","bar") :: [String]
["foo","bar"]

Done.

I can see the benefit in being able to explicit limit the traversal depth (to 0 in particular, or perhaps more generally). But having an arbitrary cut-off in the default case is a bit less convincing, because I can imagine someone having a traversal that reached the leaves in less than 25 steps, but after refactoring, no longer making the cut. And debugging that would not be fun.

Would it be a huge pain to support both the infinite and finite traversal depth cases? It would be fun if we could define

type family Infinity :: Nat where Infinity = 1 + Infinity

but I'm pretty sure that will send GHC into a spin.

25 looks arbitrary, but I've set it to not trigger reduction stack overflow.

λ> toListOf (gplateDepth @28) (replicate 100 'a') :: [Char]

<interactive>:7:11: error:
    • Reduction stack overflow; size = 201
      When simplifying the following type:
        GPlated
          0
          (GHC.Generics.M1
             GHC.Generics.S
             ('GHC.Generics.MetaSel
                'Nothing
                'GHC.Generics.NoSourceUnpackedness
                'GHC.Generics.NoSourceStrictness
                'GHC.Generics.DecidedLazy)
             (GHC.Generics.Rec0 Char))
          Char
      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 first argument of ‘toListOf’, namely ‘(gplateDepth @28)’
      In the expression:
          toListOf (gplateDepth @28) (replicate 100 'a') :: [Char]
      In an equation for ‘it’:
          it = toListOf (gplateDepth @28) (replicate 100 'a') :: [Char]

though you make a good point that it's better to get error about reduction stack overflow after refactoring than an incorrect runtime behavior.

We can increase it to e.g. 100 (maybe 1000), higher depth is most likely impractical due to compilation time and code size blow up.

Interestingly enough GHCi doesn't like it with very large depths.

λ> toListOf (gplateDepth @10000) (replicate 10000 'a') :: [Char]
ghc: panic! (the 'impossible' happened)
  (GHC version 8.10.2:
        stack depth overflow

Please report this as a GHC bug:  https://www.haskell.org/ghc/reportabug

Okay, indeed I guess once you get to say 1000, there's little risk of actually hitting the limit. And it looks like you may have stumbled on a reproducer for https://gitlab.haskell.org/ghc/ghc/-/issues/14535? Apparently the bytecode generator assumes a stack depth of 65535 should be enough for anyone. 😉 https://gitlab.haskell.org/ghc/ghc/-/blob/a1f34d37b47826e86343e368a5c00f1a4b1f2bce/compiler/GHC/CoreToByteCode.hs#L447-452

Ah, interesting. Right, that sounds like an easy way to trigger that.

Note that I actually removed depth limitation in recent commits (for explanation see #358 (comment))