Generics: Current status of syb with class

Question

I'm trying to use generic programming as described in the paper Scrap Your Boilerplate with class. That is, being able to "recurse" down with the members of a user-defined class, as opposed to a fixed set of types that are known when the traversal code is written.

It appears the corresponding hackage package http://hackage.haskell.org/package/syb-with-class can be used for this purpose, but most of the online discussion (for instance this question from 7 years ago: Does the current SYB permit extension of generic functions with new types?) implies current GHC.Generics to be preferred. In particular, that implementation seems to predate the use of constraint-kinds which is supposed to make this sort of programming easier. However, the GHC.Generics framework does not seem to permit traversals with extensible functions.

What's the best alternative these days for doing generic functions with extensible types? If at all possible, I'd like to avoid using "internal" representations (i.e., any sort of K1, M1 etc. combinators) and would love to be able to use a Uniplate like interface. Any pointers to papers, blog-posts, or general advice would be appreciated.

Answer 1

Well, here's a blog post for you...

If you want to do generic programming as described in the "Scrap Your Boilerplate with class" paper, then the recommended method is to use the syb-with-class package, notwithstanding that Stack Overflow answer, since the syb-with-class package is actively maintained and works just fine.

If you want to do generic programming with extensible types directly with GHC.Generics, then -- as with any other direct use of GHC.Generic -- you can't really avoid using the K1, M1, etc. representation. It's unfortunate that the documentation makes this representation sound like an internal implementation detail that is subject to change at any minute.

The potential advantage of GHC.Generics is that it's naturally type-class-based, so you get the type extensibility for free. For example, to take the gsize example from the SYB with class paper, you can implement it in GHC.Generics directly with a pair of classes, one for handling the generic structure, and another for handling the specific types along the way:

-- Handle the generic structure
class Size' f where
  size' :: f p -> Int
instance (Size' f) => Size' (M1 i c f) where
  size' (M1 x) = size' x
instance (Size' f, Size' g) => Size' (f :+: g) where
  size' (L1 x) = size' x
  size' (R1 x) = size' x
instance (Size' f, Size' g) => Size' (f :*: g) where
  size' (f :*: g) = size' f + size' g
instance (Size' U1) where
  size' U1 = 0  -- constructor already counted by Size class
instance (Size' V1) where
  size' _ = undefined
instance (Size c) => Size' (K1 i c) where
  size' (K1 x) = size x

-- Handle the types
class Size t where
  size :: t -> Int
  default size :: (Generic t, Size' (Rep t)) => t -> Int
  size t = 1 + size' (from t)

Generally, there would be no need to extend Size', as it's -- by construction -- a type-agnostic, generic implementation that will have an exhaustive (or nearly exhaustive) set of instances. However, the Size type class is, obviously, open and can be extended at will:

data Name = N String
instance Size Name where
    size (N _) = 1

-- a fanciful example of a custom recursive type
newtype Negative a = Neg a
instance Size a => Size (Negative a) where
  size (Neg x) = -size x

-- a user-defined type using a default instance
data Something = Something Int (Name, Name) Bool deriving (Generic)
instance Size Something

-- needs some supporting default instances:
instance Size Bool
instance (Size a, Size b) => Size (a,b)
-- and a custom instance.  This could be defaulted, but
-- then we'd need an instance for unboxed Int#
instance Size Int where size _ = 1

main = do
  print $ size (Something 10 (N "John", N "Doe") False)
  print $ size (Neg (1 :: Int, 2 :: Int), True)

Because the generic Size' class is indeed generic, it's possible to generalize it to an "SYB with class"-like query, and we can use ConstraintKinds to make the syntax a little clearer:

class Query' cls f where
  gmapQm :: Monoid a => Proxy cls -> (forall t. cls t => t -> a) -> f p -> a
instance (Query' cls f) => Query' cls (M1 i c f) where
  gmapQm p h (M1 x) = gmapQm p h x
instance (Query' cls f, Query' cls g) => Query' cls (f :+: g) where
  gmapQm p h (L1 x) = gmapQm p h x
  gmapQm p h (R1 x) = gmapQm p h x
instance (Query' cls U1) where
  gmapQm _ _ U1 = mempty
instance (Query' cls f, Query' cls g) => Query' cls (f :*: g) where
  gmapQm p h (f :*: g) = gmapQm p h f <> gmapQm p h g
instance (cls c) => Query' cls (K1 i c) where
  gmapQm p h (K1 x) = h x

and then define multiple extensible generic queries:

class Size2 t where
  size2 :: t -> Sum Int
  default size2 :: (Generic t, Query' Size2 (Rep t)) => t -> Sum Int
  size2 t = Sum 1 <> gmapQm @Size2 Proxy size2 (from t)
instance Size2 Something
instance (Size2 a, Size2 b) => Size2 (a,b)
instance Size2 Bool
instance Size2 Int where size2 _ = 1
instance Size2 Name where size2 (N _) = 1

class Tags t where
  tags :: t -> [String]
  default tags :: (Generic t, Query' Tags (Rep t)) => t -> [String]
  tags t = gmapQm @Tags Proxy tags (from t)
instance Tags Something
instance (Tags a, Tags b) => Tags (a,b)
instance Tags Name where tags (N str) = ["Name", str]
instance Tags Int where tags _ = ["Int"]
instance Tags Double where tags _ = ["Double"]
instance Tags Bool where
  tags True  = ["Bool:True"]
  tags False = ["Bool:False"]

main2 = do
  print $ size2 (Something 10 (N "John", N "Doe") False)
  print $ tags (Something 10 (N "John", N "Doe") False)

The full code with a bonus gmapT implementation and example:

{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE DefaultSignatures #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE RankNTypes #-}

import GHC.Generics
import Data.Proxy
import Data.Monoid

--
-- Size'/Size directly implemented with GHC.Generics
---

-- Handle the generic structure
class Size' f where
  size' :: f p -> Int
instance (Size' f) => Size' (M1 i c f) where
  size' (M1 x) = size' x
instance (Size' f, Size' g) => Size' (f :+: g) where
  size' (L1 x) = size' x
  size' (R1 x) = size' x
instance (Size' f, Size' g) => Size' (f :*: g) where
  size' (f :*: g) = size' f + size' g
instance (Size' U1) where
  size' U1 = 0
instance (Size' V1) where
  size' _ = undefined
instance (Size c) => Size' (K1 i c) where
  size' (K1 x) = size x

-- Handle the types
class Size t where
  size :: t -> Int
  default size :: (Generic t, Size' (Rep t)) => t -> Int
  size t = 1 + size' (from t)

data Name = N String deriving (Show)
instance Size Name where
    size (N _) = 1

-- a fanciful example of a custom recursive type
newtype Negative a = Neg a
instance Size a => Size (Negative a) where
  size (Neg x) = -size x

-- a user-defined type using a default instance
data Something = Something Int (Name, Name) Bool deriving (Show, Generic)
instance Size Something

-- needs some supporting default instances:
instance Size Bool
instance (Size a, Size b) => Size (a,b)
-- and a custom instance.  This could be defaulted, but
-- then we'd need an instance for unboxed Int#
instance Size Int where size _ = 1

--
-- gmapQm "with class" implemented using GHC.Generics and ConstraintKinds
--

class SYB cls f where
  gmapQm :: Monoid a => Proxy cls -> (forall t. cls t => t -> a) -> f p -> a
  gmapT :: Proxy cls -> (forall t. cls t => t -> t) -> f p -> f p
instance (SYB cls f) => SYB cls (M1 i c f) where
  gmapQm p h (M1 x) = gmapQm p h x
  gmapT p h (M1 x) = M1 $ gmapT p h x
instance (SYB cls f, SYB cls g) => SYB cls (f :+: g) where
  gmapQm p h (L1 x) = gmapQm p h x
  gmapQm p h (R1 x) = gmapQm p h x
  gmapT p h (L1 x) = L1 $ gmapT p h x
  gmapT p h (R1 x) = R1 $ gmapT p h x
instance (SYB cls U1) where
  gmapQm _ _ U1 = mempty
  gmapT _ _ U1 = U1
instance (SYB cls f, SYB cls g) => SYB cls (f :*: g) where
  gmapQm p h (f :*: g) = gmapQm p h f <> gmapQm p h g
  gmapT p h (f :*: g) = gmapT p h f :*: gmapT p h g
instance (cls c) => SYB cls (K1 i c) where
  gmapQm p h (K1 x) = h x
  gmapT p h (K1 x) = K1 (h x)

-- Size query using gmapQm

class Size2 t where
  size2 :: t -> Sum Int
  default size2 :: (Generic t, SYB Size2 (Rep t)) => t -> Sum Int
  size2 t = Sum 1 <> gmapQm @Size2 Proxy size2 (from t)
instance Size2 Something
instance (Size2 a, Size2 b) => Size2 (a,b)
instance Size2 Bool
instance Size2 Int where size2 _ = 1
instance Size2 Name where size2 (N _) = 1

-- another generic query using gmapQm

class Tags t where
  tags :: t -> [String]
  default tags :: (Generic t, SYB Tags (Rep t)) => t -> [String]
  tags t = gmapQm @Tags Proxy tags (from t)
instance Tags Something
instance (Tags a, Tags b) => Tags (a,b)
instance Tags Name where tags (N str) = ["Name", str]
instance Tags Int where tags _ = ["Int"]
instance Tags Double where tags _ = ["Double"]
instance Tags Bool where
  tags True  = ["Bool:True"]
  tags False = ["Bool:False"]

-- a generic transform

class Zero t where
  zero :: t -> t
  default zero :: (Generic t, SYB Zero (Rep t)) => t -> t
  zero t = to $ gmapT @Zero Proxy zero (from t)
instance Zero Something
instance (Zero a, Zero b) => Zero (a,b)
instance Zero String where zero _ = []  -- zero strings
instance Zero Name where zero = id -- but don't zero names!
instance Zero Bool where zero _ = False
instance Zero Int where zero _ = 0
instance Zero Double where zero _ = 0

-- some tests

main = do
  let s = Something 10 (N "John", N "Doe") False
  print $ size s
  print $ size (Neg (1 :: Int, 2 :: Int), True)
  print $ size2 s
  print $ tags s
  print $ zero (s, "this string will be zeroed")