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

[Alexey Rodriguez]

Hey Claus! Sorry for the delay, just after the deadline I got into two more
deadlines so I was very busy with paper writing these last weeks!

On Fri, Jun 27, 2008 at 10:48 PM, Claus Reinke <claus.reinke at talk21.com>
wrote:

>
>
>
>  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.


Yes, it looks like sort of defining a local type constant which should not
be visible after the transformation.


>
>
>  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:-).


As I said before, I don't consider this an elegant use of unsafeCoerce. The
reason is that if you later want to generalize other functions over type
constructors (for example, zipWith), you have to again deal with
unsafeCoerce. It would already be a slight improvement if this trick can be
encapsulated into a reusable combinator.

If you want to make SYB support definitions that abstract over type
constructors, you may want to have a look at "Scrap your Boilerplate
Revolutions". Although, I don't immediately see a way to generalize gfoldl
in order to encode the "lifted spine view".


>
>
> 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.


Yes, I think I would also prefer those instances to reside in a separate
module, so that you can choose not to import them.


>
>
> 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.


Probably this is something you have to prove whenever you define a generic
function in this style.



>
>
> 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.


I think it's good to see how far the limits of SYB and other libraries can
be pushed. But I would personally avoid using gmap as you proposed, until
there is a cleaner way to do things or the corner cases are well understood.


>
>
> 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)?


That gives rise to another type transforming map, namely bimap. You can look
at its Generic Haskell definition at this URL:

https://svn.cs.uu.nl:12443/repos/Generic-Haskell/trunk/Generic-Haskell/lib/GH/Prelude.ghs

Cheers,

Alexey
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/generics/attachments/20080721/437902ef/attachment-0001.htm