[Hs-Generics] Re: gMap in SYB1

Claus Reinke claus.reinke at talk21.com
Wed Jul 2 06:11:39 EDT 2008

>> It has occurred to me a year ago that the type-changing gMap
>> is easily possible in SYB. The recent discussion has prompted me to
>> implement that solution. I have committed a patch to
>> http://darcs.haskell.org/generics/comparison/SYB1_2/GMap.lhs
>> gmap :: (Data a, Data b, Data x, Data y) => (a -> b) -> x -> y
> Perhaps we can combine our versions to get the best of both?

To wit:

    data X = X deriving (Data,Typeable)
    data Y = Y deriving (Data,Typeable)
    fmap'' :: (Data (f X), Data (f Y)) => (a -> b) -> f a -> f b
    fmap'' f = markTheSpots (gmap (wrap f))
      where wrap :: (a->b) -> (X->Y)
            wrap = unsafeCoerce
            markTheSpots :: (f X -> f Y) -> (f a -> f b)
            markTheSpots = unsafeCoerce

so that:

    *GMap> gmap not (True,True) :: (,) Bool Bool
    *GMap> fmap'' not (True,True) :: (,) Bool Bool

fmap'' is safer than the original fmap', in that trying to
map over functions will run into the gunfold runtime
error, eg:

    *GMap> fmap'' (\True->'c') (id::Bool->Bool) True
    *** Exception: gunfold

I keep worrying that I should do something more to hide
X/Y, perhaps similar to the runST trick, but (a) while it
was easy to show type-unsafety in fmap' in the presence
of non-traversing Data instances, I have yet to find an 
example exposing X/Y in fmap'', and (b) pretending
to be fully polymorphic is not necessarily appropriate in
a generic programming context;-) 

So using specific, but unknown types doesn't feel entirely
wrong. gmap doesn't know about X/Y, so can only treat 
them generically, and the same goes for f, if X/Y aren't 
exported. Of course, the generic toolbox allows to 
recover the types, but f never sees X/Y, and gmap 
doesn't seem to care:

    *GMap> fmap'' dataTypeOf (True,True) :: (,) Bool DataType
    (True,DataType {tycon = "Prelude.Bool", datarep = AlgRep [False,True]})

    *GMap> fmap'' (\X->Y) (True,True) :: (,) Bool Y

        Couldn't match expected type `X' against inferred type `Bool'
        In the expression: True
        In the second argument of `fmap''', namely `(True, True)'
        In the expression: fmap'' (\ X -> Y) (True, True) :: (,) Bool Y

    *GMap> fmap'' (fmap'' not) [(True,Just True,True)]
    [(True,Just True,False)]

    *GMap> fmap'' (gmap not) [(True,Just True,True)]::[(Bool,Maybe Bool,Bool)]
    [(False,Just False,False)]

Still, the problem with these kinds of proofs is not to show
that the cases one has thought of are safe, but to be sure
that there are no unsafe cases one hasn't thought of. So,
more minds/eyeballs are welcome!-)


ps. gmap itself is somewhat tricky to use, depending on
    type information from the context, and failing with 
    runtime errors if that type information doesn't match.

    *GMap> gmap not (True,True) :: (Bool,Char)
    (False,*** Exception: gunfold

    But then, SYB generally operates at the borders
    of type safety (what one would expect to be a
    type error often just leads to unexpected behaviour
    - there are so few gaps between well-typed SYB
    programs that the type system, instead of noting
    that things go wrong, can only cause things to go

    Are the other generic programming libraries better
    behaved in this area?

More information about the Generics mailing list