1

How to extract an identifier (in this case an integer) from a structure using GHC.Generics?

I have an Id type:

newtype Id = Id { _id :: Int }

and a lot of types that use that type:

data VarId = VarId Name Id SortId
data FuncId = FuncId Name Id [SortId] SortId
data SortId = Name Id
-- ... and 20 more of these things

On top of that there are other types that wrap the types above, for instance, identifiers:

data Identifier = IdVar VarId
                | IdFunc FuncId
                | IdSort SortId
                -- ... and 20 more of these things

Now I need to extract the _id field from any of these types containing an Id value. Currently we have tons of boilerplate for this, and I want to scrap it away using generics.

At first I thought about defining a class:

class Identifiable e where
    getId :: e -> Id

    default getId :: (Generic e, GIdentifiable (Rep e)) => e -> Id
    getId = gGetId . from

class GIdentifiable f where
    gGetId :: f e -> Id

in such a way that you'd have an Identifiable instance only if there is one such Id type inside (in case that there are multiple of those like in FuncId above we return the first Id found when traversing the structure from top to bottom). Now the problem comes when I try to define the GIdentifiable instances for the product and sum. I would like to express something like:

instance (GIdentifiable a) => GIdentifiable (a :*: b) where
    gGetId (a :*: _) = gGetId a

instance {-# OVERLAPS #-} (GIdentifiable b) => GIdentifiable (a :*: b) where
gGetId (_ :*: b) = gGetId b

Which won't work because I'm defining duplicate instances.

I could redefine Identifiable so that getId :: e -> Maybe Id but this will remove some of the type safety, and introduce unnecessary checks when I know that a type contains at least one Id.

Is there a way to express this sort of case analysis when working with the type system?

Damian Nadales
  • 4,907
  • 1
  • 21
  • 34
  • You can use a closed type family to do the instance resolution. I would probably define a datatype representing the location of an `Id` in the structure and a type family producing values of that type. Then you can make instances of an auxiliary class follow that path. – dfeuer Nov 23 '17 at 17:25
  • Do you have any references that I can read? Should I just lookup "type families"? – Damian Nadales Nov 23 '17 at 17:38
  • 1
    I don't have time to help you find a good source right now, unfortunately. You may learn something from https://ghc.haskell.org/trac/ghc/ticket/14255#comment:5 but there are definitely better examples out there (including a few in questions I've answered here). – dfeuer Nov 23 '17 at 17:48
  • 1
    I think some sort of `Maybe`-like version is almost certainly necessary even to define a very certain version. Suppose you have `(x,y)`. This is certain to have an `Id` if and only if `x` or `y` is certain to have an `Id`. But if `y` is certain to have an `Id` and `x` *might* have an `Id`, then you want to check `x` first. There's going to be some kind of intertwined logic, I expect. Of course, this is only an issue if you have sum types around that can sometimes have an `Id` and sometimes not.... – dfeuer Nov 27 '17 at 23:50
  • I'm trying using `type-families` but [I'm hitting the wall](https://stackoverflow.com/questions/47653880/using-type-families-and-generics-to-find-an-id-value) when I try to combine type-families with GHC.Generics :/ – Damian Nadales Dec 05 '17 at 12:41
  • The wall I hit was really figuring out exactly what you wanted to do. Think particularly hard about what you want the constraint to be on `K1`. – dfeuer Dec 05 '17 at 18:32

0 Answers0