[Hs-Generics] Traversable Functor Data,or: X marks the spot

[Claus Reinke]

Hi Alexey,

> We have a deadline coming soon, so this is only a brief comment about your
> GMap implementation.

Thanks, the silence had me worried! I'll wait till next week, then, 
meanwhile just a few comments on your comments;-)
 
> wanted to see whether the second argument of Tricky would be (incorrectly)
> transformed to Bool. But it turned out that fmap' behaved as expected. So I

That's the idea - the wrapped function parameter will be delivered
everywhere by the SYB framework, but will only be applied to the 
marked type. The marker type should play no other role.

> On the other hand, I think that using unsafeCoerce as a way to define
> generic functions is inelegant and probably bad practice due to possible
> runtime failures. However, I must admit that I was surprised when I saw your
> trick :).

Haskell is full of odd corners (eg, the IO model is not backed up 
by a uniqueness type system, so is really unsafe under the abstraction,
and neither the implementation nor the optimizer are verified by the
type system; the Typeable stuff only works by convention for the
instances; ..).

Ideally, the language/type system will be extended to be able to
express all the capabilities of gfoldl's code in gfoldl's type. But
as long as that isn't the case, unsafeCoerce allows us to extend
the type system, just as unsafePerformIO allows us to extend
the evaluator. But since we are dealing in extensions, it is up to
us to demonstrate that we haven't broken anything (well, me,
in this case, but after staring at gfoldl's type and its implication
for several days, I felt like calling for a little outside perspective:-).

My assumption was roughly that 'everywhere f' would apply
'f' to all occurences typed 'a' provided that 'f' has 'a' generic
special case for type 'a'. That assumption is violated by the
Data instances for (a->b) and (IO a), so as long as those
instances exist, it is easy to come up with counterexamples
for fmap'. That is why I was asking for the rationale for those
instances - if it was just convenience, they should be dropped,
especially since SYB doesn't permit overloading to polymorpic
types, so those default instances are not easily bypassed.

Once that is sorted, the next issue is whether the private
marker type can escape and be observed by other means.
fmap' is constructed in such a way that neither 'f' nor the
calling context see 'X', so as long as the generic scaffolding
provided by 'Data' doesn't mess up, that should be fine.

For things like traverse', other operators might be applied
to things coerced to 'X', so that needs to be looked into
and perhaps improved.

> Probably we'll get back to you around next week. Meanwhile, you may find
> useful to look at the paper we wrote on comparing generic programming
> libraries[1]. In particular, you can look at caveats that apply to SYB.

Yep, I guess I'll have to look through some more of the
generic papers on my reading heap:-) Btw, the overall idea
behind my experiment is whether we can use 'Data/Typeable',
which can be derived in GHC, to avoid the need for
deriving support for other generic instances (such as Functor,
Traversable). Again, a very pragmatic perspective (what
can we do with the basis we have now, rather than: what
better basis would be like to have?), but closely related to
this list's aim of a unified generic programming framework.

Btw, expanding SYB's invariant maps to variant ones raises the 
whole issue of co- vs contra-variance: if one really wants to 
fmap over types containing the parameter type in function types, 
one would need to handle both positive and negative occurrences, 
presumably by a pair of dual functions (a->b, b->a)?

Looking forward to more feedback after that deadline.

Thanks,
Claus