Hi Claus!<br><br>We have a deadline coming soon, so this is only a brief comment about your GMap implementation.<br><br>I played a bit with your fmap' function to see whether I could find an obvious problem with the implementation. For instance, I used this datatype:<br>
<br>data Tricky a = Tricky a Char deriving (Data,Typeable)<br><br>and tried to transform a value of type "Tricky Char" to "Tricky Bool". I 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 think that SYB can pass the GMap test.<br>
<br>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 :).<br>
<br>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.<br>
<br>Cheers,<br><br>Alexey<br><br>[1] <a href="http://www.cs.uu.nl/wiki/bin/view/Alexey/ComparingLibrariesForGenericProgrammingInHaskell">http://www.cs.uu.nl/wiki/bin/view/Alexey/ComparingLibrariesForGenericProgrammingInHaskell</a><br>
<br><div class="gmail_quote">On Tue, Jun 24, 2008 at 8:45 PM, Claus Reinke <<a href="mailto:claus.reinke@talk21.com">claus.reinke@talk21.com</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Dear Generics;-)<br>
<br>
this is a repost from cvs-libraries of an experiment which you might find of interest, and on which I'd welcome feedback. One impact being that SYB can implement your GMap test (on which it currently defaults), among other things (see message 1 below, the technique probably applies to Uniplate as well?). One issue being that Data instances for non-algebraic types that default to<br>
doing nothing render this technique unsafe (see message 2 below).<br>
<br>
Btw, the announcement of the unified generics library project was so long ago that I had forgotten about it and about this list (thanks to Simon PJ for reminding me). My interest in this is partially from my past with HaRe, partially from wanting generic traversal support over GHC AST types, so I'm more interested<br>
in generic traversal/analysis style libraries.<br>
<br>
Claus<br>
<br>
--------- message 1<br>
<br>
The issue at hand: can we use Data/Typeable to do what Functor and Traversible do so easily, namely type-changing maps? Or should<br>
there be support for deriving all of Data/Typeable/Functor/Traversible<br>
over GHC's AST?<br>
<br>
A drastically simplified example from David's Haddock 2 code<br>
(Haddock.Interface.Rename) needs to do a kind of mapM<br>
<br>
renameDoc :: Monad m => HsDoc Name -> m (HsDoc DocName)<br>
<br>
which is straightforward with Traversible, but that is not derivable<br>
yet (David has been working on that, though), while the usual basis<br>
of SYB, Data/Typeable, is derivable, but all SYB transformations are based on gfoldl, the type of which does not permit type-changing maps:<br>
<br>
gfoldl :: (Data a) =>(forall a1 b. (Data a1) => c (a1 -> b) -> a1 -> c b)<br>
-> (forall g. g -> c g)<br>
-> a-> c a<br>
<br>
One could probably go from heterogeneous Data types to a<br>
homogeneously typed tree representation, do the map there, then transform back, but that would require additional overhead<br>
and a type coercion for the backtransform. Also, it seems a pity that the derived code for gfoldl can handle such maps - it is just<br>
gfoldl's type that gets in the way (and trying to generalize that<br>
type is a whole different kind of headache..).<br>
<br>
While boilerplate scrappers around the globe eagerly await the<br>
release of <br>
"Generalizing the type of gfold, or: to braindamage and beyond"<br>
(author: unknown; release date: unknown; release: unlikely;-)<br>
<br>
I thought I'd have a go at the smaller problem of finding a way<br>
to bypass gfoldl's type systematically in order to use its derivable<br>
code for things like fmap and traverse. This message summarizes<br>
how far I've got so far, and asks for comments (does this do<br>
what it should? is it safe? assuming it can be cleaned up to do<br>
what it should in a safe way, does this mean that deriving Data/<br>
Typeable for GHCs AST types will be sufficient, or should we<br>
still have Traversible as well? etc.).<br>
<br>
First, here is an implementation of renameDoc in terms of<br>
gfoldl and unsafeCoerce (slightly cleaned up version of what<br>
I sent in the other thread earlier):<br>
<br>
data Name = Name String deriving (Show,Data,Typeable)<br>
data DocName = DocName String deriving (Show,Data,Typeable)<br>
<br>
renameDoc :: Monad m => HsDoc Name -> m (HsDoc DocName)<br>
renameDoc (DocIdentifier ids) = mapM (\(Name n)->return (DocName n)) ids >>= return . DocIdentifier<br>
renameDoc hsDoc = n2d (gfoldl k return hsDoc)<br>
where k c x = ap c (mkM (d2n . renameDoc) x)<br>
<br>
n2d :: Monad m => m (HsDoc Name) -> m (HsDoc DocName)<br>
n2d = unsafeCoerce<br>
d2n :: Monad m => m (HsDoc DocName) -> m (HsDoc Name)<br>
d2n = unsafeCoerce<br>
<br>
'DocIdentifier :: [id] -> HsDoc id' is the only constructor in HsDoc that involves the parameter type 'id', so renameDoc either does the<br>
parameter type conversion or -for other constructors- recurses into the subexpressions, using gfoldl to build a monadic map. <br>
The important insight here is that gfoldl's code can handle the task,<br>
we just pretend that our map is type-preserving to conform to gfoldl's restrictive type, by coercing the result types (inside gfoldl, we pretend that renameDoc returns a (HsDoc Name), which outside gfoldl, we coerce back to (HsDoc DocName)).<br>
<br>
Assuming that noone looks at the return types inside gfoldl (at least,<br>
not in a way that would be affected by this change in type - SYB<br>
does support adhoc overloading, after all, as in mkM here), this<br>
seems to work:<br>
<br>
testDoc = DocAppend (DocParagraph (DocAppend (DocIdentifier [Name "well-typed"]) DocEmpty)) (DocAppend (DocString "programs") (DocIdentifier [Name "don't",Name "go",Name "anywhere"]))<br>
<br>
*Main> renameDoc testDoc<br>
DocAppend (DocParagraph (DocAppend (DocIdentifier [DocName "well-typed"]) DocEmpty))<br>
(DocAppend (DocString "programs") (DocIdentifier [DocName "don't",DocName "go",DocName "anywhere"]))<br>
<br>
But can we generalize this, and what about those coercions?<br>
Can we -ideally- define something like fmap and traverse in terms of gfoldl, and hide the uglyness in their implementations?<br>
<br>
Well, I'll spare you (and me;-) the details of my struggle with<br>
the type system, and just show the results, with some comments. First, the simpler fmap:<br>
<br>
-- "X marks the spots";-) X should be private<br>
data X = X deriving (Data,Typeable)<br>
<br>
fmap' :: (Data (f X)) => (a -> b) -> f a -> f b<br>
fmap' f x = markTheSpots (rec (wrap f)) x<br>
where<br>
markTheSpots :: (f X -> f X) -> (f a -> f b)<br>
markTheSpots f = unsafeCoerce . f . unsafeCoerce<br>
rec :: (Data a) => (X -> X) -> a -> a<br>
rec f x = (gmapT (rec f) `extT` f) x<br>
wrap :: (a -> b) -> (X -> X)<br>
wrap f = unsafeCoerce . f . unsafeCoerce<br>
<br>
Surprisingly simple for something that seemed impossible<br>
at first, isn't it?-) Since we're already committed (for this<br>
experiment, at least) to some type fiddling, we can make<br>
more constructive use of unsafeCoerce, for two purposes:<br>
<br>
1. We wrap the function parameter f, to make it look<br>
like a type-preserving function, on some private type X.<br>
<br>
2. We mark the occurrences of the type constructor f's parameter type, by coercing 'f a' to 'f X' and 'f X' to<br>
'f b'.<br>
<br>
Then, we simply use SYB to apply f, when its type matches<br>
the parameter, or to recurse into the subexpressions using<br>
gmapT, otherwise. If X is private, f will only be applied<br>
to the "functor parameter" _positions_ in 'f a', not to other<br>
"functor parameter" _type_ occurrences in 'f a':<br>
<br>
*Main> fmap' not $ (True,True)<br>
(True,False)<br>
*Main> fmap' not $ [True,True]<br>
[False,False]<br>
<br>
*Main> fmap' (\(Name s)->(DocName s)) testDoc<br>
DocAppend (DocParagraph (DocAppend (DocIdentifier [DocName "well-typed"]) DocEmpty))<br>
(DocAppend (DocString "programs") (DocIdentifier [DocName "don't",DocName "go",DocName "anywhere"]))<br>
<br>
Note how we use one kind of recursion where a manual implementation of fmap would use two: handling subexpressions<br>
(which we'd usually do by pattern matching and expression<br>
construction) and functor type recursion.<br>
<br>
Ecouraged by this success, we are ready to tackle the slightly more tricky traverse, using the same techniques:<br>
mark the spot, wrap the worker, one kind of recursion.<br>
Only this time, we need to take care of the applicative<br>
plumbing as well, so it's gfoldl instead of gmapT, and<br>
some more complex types.<br>
<br>
We need the usual SYB type extension support, but for<br>
Applicative, not Monad (SYB was defined before<br>
Applicative existed, it seems..):<br>
<br>
-- type extension over Applicative f<br>
mkF :: forall f a b . (Applicative f,Typeable a,Typeable b) => (b -> f b) -> a -> f a<br>
mkF f x = case gcast (F f) of { Just (F f) -> f x; Nothing -> pure x }<br>
<br>
extF :: forall t f a b . (Typeable a,Typeable b) => (a -> f a) -> (b -> f b) -> (a -> f a)<br>
(f `extF` fspec) x = case gcast (F fspec) of { Just (F fspec) -> fspec x; Nothing -> f x }<br>
<br>
newtype F f x = F { unF :: x -> f x }<br>
<br>
And here we go:<br>
<br>
traverse' :: forall f t a b . (Applicative f,Typeable1 f,<br>
Typeable1 t,Data (t X),<br>
Typeable a)<br>
=> (a -> f b) -> t a -> f (t b)<br>
traverse' f x = markTheSpots (rec (wrap f)) x<br>
where<br>
markTheSpots :: forall a b . (t X -> f (t X)) -> (t a -> f (t b))<br>
markTheSpots f = unsafeCoerce . f . unsafeCoerce<br>
wrap :: forall a b . (a -> f b) -> (X -> f X)<br>
wrap f = unsafeCoerce . f . unsafeCoerce<br>
<br>
rec :: forall x . Data x => (X -> f X) -> x -> f x<br>
rec f x = (gfoldl (k f) z `extF` f) x k :: forall a b . Data a => (X -> f X) -> f (a -> b) -> a -> f b<br>
k f c x = c <*> (mkF (rec f :: Data a => a -> f a) `extF` f) x<br>
z c = pure c<br>
<br>
This does seem to do the right thing, so I don't seem to be<br>
completely on the wrong track:<br>
<br>
*Main> traverse' (pure . not) (True,True)<br>
(True,False)<br>
<br>
*Main> traverse' (pure . not) [True,True]<br>
[False,False]<br>
<br>
*Main> traverse' print testDoc<br>
Name "well-typed"<br>
Name "don't"<br>
Name "go"<br>
Name "anywhere"<br>
DocAppend (DocParagraph (DocAppend (DocIdentifier [()]) DocEmpty)) (DocAppend (DocString "programs") (DocIdentifier [(),(),()]))<br>
<br>
*Main> traverse' (pure) testDoc<br>
DocAppend (DocParagraph (DocAppend (DocIdentifier [Name "well-typed"]) DocEmpty)) (DocAppend (DocString "programs") (DocIdentifier [Name "don't",Name "go",Name "anywhere"]))<br>
<br>
*Main> traverse' (pure . (\(Name s)->DocName s)) testDoc<br>
DocAppend (DocParagraph (DocAppend (DocIdentifier [DocName "well-typed"]) DocEmpty))<br>
(DocAppend (DocString "programs") (DocIdentifier [DocName "don't",DocName "go",DocName "anywhere"]))<br>
<br>
but I'm too battered from trying to coerce gfoldl to analyze this<br>
properly at the moment, so I'm sending this in the hope of (a)<br>
not having to look at gfoldl's type for a while !-) and (b) getting<br>
some feedback (is this useful? does the extra overhead matter?..), caveats (cyclic programs, nested traversals, escaping Xs, ..?), etc.<br>
<br>
Over to you,<br>
Claus<br>
<br>
PS. the "X marks the spot" trick reminds me of the popular<br>
medicine topic: delivery system plus targeted activation<br>
(SYB plus unsafeCoerce).<br>
<br>
------------- message 2<br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
fmap' :: (Data (f X)) => (a -> b) -> f a -> f b<br>
fmap' f x = markTheSpots (rec (wrap f)) x<br>
where<br>
markTheSpots :: (f X -> f X) -> (f a -> f b)<br>
markTheSpots f = unsafeCoerce . f . unsafeCoerce<br>
rec :: (Data a) => (X -> X) -> a -> a<br>
rec f x = (gmapT (rec f) `extT` f) x<br>
wrap :: (a -> b) -> (X -> X)<br>
wrap f = unsafeCoerce . f . unsafeCoerce<br>
</blockquote>
.. <br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
1. We wrap the function parameter f, to make it look<br>
like a type-preserving function, on some private type X.<br>
<br>
2. We mark the occurrences of the type constructor f's parameter type, by coercing 'f a' to 'f X' and 'f X' to<br>
'f b'.<br>
<br>
Then, we simply use SYB to apply f, when its type matches<br>
the parameter, or to recurse into the subexpressions using<br>
gmapT, otherwise. If X is private, f will only be applied<br>
to the "functor parameter" _positions_ in 'f a', not to other<br>
"functor parameter" _type_ occurrences in 'f a'<br>
</blockquote>
<br>
..but f might not be applied at all, which leads to the first<br>
issue with this technique:<br>
<br>
I was surprised to see Data instances for (a->b) and IO a, since for such non-algebraic types, there isn't anything to gfoldl or gmap over. And those instances do indeed seem<br>
to offer very little functionality (not to mention the runtime<br>
errors..). <br>
For fmap'/traverse', this means that f will not be applied, and so it is not a good idea to coerce the types as if f had been applied (because the hidden parameter could be exposed after traversal, with changed type and unchanged<br>
representation!).. So we need to restrict the types of fmap'/traverse'. Which leads to two questions:<br>
<br>
- what is the rationale for having these non-functional<br>
Data instances?<br>
<br>
If one is to have 'instance Data (a->b)', is there a way<br>
to make it more functional?<br>
<br>
- how can we capture algebraic types in a type (class)?<br>
<br>
I thought that Data would do just that, being designed<br>
to gfoldl over concrete data constructors, but apparently<br>
not. And I don't really want to have a separate list of all the types for which Data works, or of all the types for which Data doesn't quite work.<br>
<br>
Claus<br>
<br>
ps. What is the right list for this topic?<br>
<br>
<br>
_______________________________________________<br>
Generics mailing list<br>
<a href="mailto:Generics@haskell.org" target="_blank">Generics@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/generics" target="_blank">http://www.haskell.org/mailman/listinfo/generics</a><br>
</blockquote></div><br>