Generic programming in Haskell with SYB and ad-hoc polymorphism

Question

I have a class identical to Show and I would like to make an instance of this class for each tuple type. Usually this is done by writing separately instances for each tuple type

instance  (Show a, Show b) => Show (a,b)  where
  showsPrec _ (a,b) s = show_tuple [shows a, shows b] s

instance (Show a, Show b, Show c) => Show (a, b, c) where
  showsPrec _ (a,b,c) s = show_tuple [shows a, shows b, shows c] s

instance (Show a, Show b, Show c, Show d) => Show (a, b, c, d) where
  showsPrec _ (a,b,c,d) s = show_tuple [shows a, shows b, shows c, shows d] s
...

Writing one instance per tuple type results in a lot of boilerplate and it's easy to see the common pattern shared among all the showPrec implementations. To avoid this kind of boilerplate I thought I could use Data.Generics from Scrap your boilerplate and implement a folding over tuples, like

showTuple = intercalate " " . gmapQ ("" `mkQ` show)

But showTuple doesn't work for some reason

> showTuple (1,2)
" "

I think the problem is the fact that show is polymorphic because if I specialize showTuple then it works

showTupleInt = intercalate " " . gmapQ ("" `mkQ` (show :: Int -> String))

> showTupleInt (1::Int,2::Int)
"1 2"

I have checked the code of gshow that does something similar to what I need, but I can't figure out how it works. If I try to import its code into GHCI I get an error:

> let gshows = (\t -> showChar '('
                      . (showString . showConstr . toConstr $ t)
                      . (foldr (.) id . gmapQ ((showChar ' ' .) . gshows) $ t)
                      . showChar ')'
                      ) `extQ` (shows :: String -> ShowS)
<interactive>:262:59:
Could not deduce (a ~ d)
from the context (Data a)
  bound by the inferred type of
           gshows :: Data a => a -> String -> String
  at <interactive>:(259,5)-(264,44)
or from (Data d)
  bound by a type expected by the context:
             Data d => d -> String -> String
  at <interactive>:262:33-65
  `a' is a rigid type variable bound by
      the inferred type of gshows :: Data a => a -> String -> String
      at <interactive>:259:5
  `d' is a rigid type variable bound by
      a type expected by the context: Data d => d -> String -> String
      at <interactive>:262:33
Expected type: d -> String -> String
  Actual type: a -> String -> String
In the second argument of `(.)', namely `gshows'
In the first argument of `gmapQ', namely
  `((showChar ' ' .) . gshows)'
In the second argument of `(.)', namely
  `gmapQ ((showChar ' ' .) . gshows)'

So I have two questions:

1. what's wrong with showTuple and how can I fix it such that it will work with tuples of any size
2. how gshow works and why if I import its code on GHCI I get that error?

EDIT: I'm studying Data.Generics and in general SYM, so I would like to use that module. I will accept an answer only if it uses just that module. Thanks.

Hittite

Answer 1

You're right that showTuple doesn't work because of the polymorphism of show. The problem is that mkQ wants to pick out one specific type:

mkQ :: (Typeable a, Typeable b) => r -> (b -> r) -> a -> r

The b in the type signature has to be one specific type for each use of mkQ - without the type signature the defaulting rules are probably picking something (not sure what!), whereas with the type signature it picks Int.

Your showTupleInt does work on tuples of any size, but of course not on tuples of any type.

The problem with defining gshows in GHCi is that it really needs a type signature to be able to type check, because of the recursive use of gshows in its own definition at a different type to the original invocation. Without the type signature the type-checker wants the definition of gshows to have exactly the same instantiation of the type variable as the use of gshows - which shows up as the Could not deduce (a ~ d) type error.

You can see this by putting it in a source file with and without the type signature - with the signature it typechecks fine, without it you get a similar error to the one you got, if you first use :set -XNoMonomorphismRestriction.

gshows works at all because of the type of gmapQ:

gmapQ :: Data a => (forall d. Data d => d -> u) -> a -> [u]

In contrast to mkQ, the parameter it takes is itself polymorphic - note the nested forall.

Although your showTuple also uses gmapQ, it's too late - mkQ has already caused the trouble by forcing show to only work on one type.

You also can't use show directly with gmapQ directly because the constraints are different - gmapQ wants something that will work on any instance of Data, whereas show is constrained by Show. gshows never actually uses the Show type class generically, although it does use shows specialised to String.

It's difficult to prove a negative in a case like this, but I'm fairly sure that you can't write anything like showTuple that will use the Show class polymorphically using just syb, because it simply doesn't have anything that can "recognise" types that have a particular instance. That's why syb-with-class exists.

Also, if you really do want something that just works on a single level of the type structure, i.e. shows any size tuple but uses something else for the elements of the tuple, then syb is arguably the wrong solution because it is designed for operating recursively and finding things at any level of a data structure. My view is that the GHC.Generics solution is the nicest one for implementing showTuple.

Needham

Your explanation is very clear, thank you! Ok, not I understand why it is not working. What I don't understand from your answer is if it is possible to implement showTuple even by changing the code completely (remove gmapQ maybe?) but by using Data.Generics. If you can provide or explain why is not possible I will accept the answer. – Hittite

Answer 2

I'm more familiar with GHC Generics, rather than with SYB, so I'm offering a solution based on Generics. While it doesn't directly answer your question, I hope it could be also useful.

{-# LANGUAGE TypeOperators, FlexibleContexts, DefaultSignatures #-}
import Data.Sequence
import GHC.Generics

class Strs' f where
    strings' :: f a -> Seq String

instance Strs' U1 where
    strings' U1 = empty

instance Show c => Strs' (K1 i c) where
    strings' (K1 a) = singleton $ show a

instance (Strs' a) => Strs' (M1 i c a) where
    strings' (M1 a) = strings' a

instance (Strs' f, Strs' g) => Strs' (f :*: g) where
    strings' (a :*: b) = strings' a >< strings' b

class Strs a where
    strings :: a -> Seq String
    default strings :: (Generic a, Strs' (Rep a)) => a -> Seq String
    strings = strings' . from

-- Since tuples have Generic instances, they're automatically derived using
-- the above default.
instance Strs () where
instance (Show a, Show b) => Strs (a, b) where
instance (Show a, Show b, Show c) => Strs (a, b, c) where

Sainthood

I like your implementation using GHC.Generics but I can't accept it because it uses another module. I would like to use Data.Generics. – Hittite

@Hittite No problem, I just wanted to chip in my 2¢. Hopefully somebody else more fluent with SYB will provide the full answer. – Sainthood

Answer 3

You could use syb-with-class. It predates -XConstraintKinds, so you need to write an instance of a Sat class and derive the Data class that this library derives. Here is an example, that's pretty close to the showTuple example, except I add some {}:

{-# LANGUAGE FlexibleContexts, FlexibleInstances, MultiParamTypeClasses, TemplateHaskell, UndecidableInstances #-}
import Data.Generics.SYB.WithClass.Basics
import Data.Generics.SYB.WithClass.Instances
import Data.Generics.SYB.WithClass.Derive

data A a b c = A a b c deriving Show
data B a = B a deriving Show
data C a = C a deriving Show

derive [''A,''B,''C]

data ShowD a = ShowD { showD :: a -> String -> String }
instance (Show a) => Sat (ShowD a) where
    dict = ShowD shows

gshow x = case gfoldl ctx 
                (\ (s, f) x -> (s . ("{"++) . showD dict x . ("}"++) , f x))
                (\y -> (id ,y))
                x
        of (str,_) -> str ""
    where
        ctx :: Proxy ShowD
        ctx = undefined

x1 = A (B 'b') (C "abc") (B ())

{-
>>> gshow x1
"{B 'b'}{C \"abc\"}{B ()}"

>>> show x1
"A (B 'b') (C \"abc\") (B ())"
-}

The second argument to gfoldl gets to call shows (B 'b'), shows (C "abc") and shows (B ()) thanks to the showD dict which gets the shows function with the correct type.

Reamer

Thanks @aavogt, your proposal is very interesting. I don't accept it only because it requires another module. I would like to avoit using another module on top of SYM just for this. If you have a solution using only Data.Generics then I will be happy to accept your answer. – Hittite

@mariop, I think the best you can do with SYB is to list out types that you know have Show instances at one point. For example mkQ "" (show :: Integer -> String) `extQ` (show :: Int -> String) `extQ` (show :: Double -> String) :: GenericQ String can be supplied to gmapQl to show those three types. That's pretty limited, since there are many possible types you might forget ([[[[(Int,Double,String)]]]] has a Show instance) or be unable to list (since they not defined yet). But maybe extQ is good enough for you. – Reamer