Support type synonyms in datatypes about generics-mrsop

[VictorCMiraldo]

@arianvp

how much do we want this feature? This will be much harder to achieve mainly because of how the
algorithm is structured. The problem lies in the fact that even a type synonym with no args
might require some beta-reduction to be correctly reified, ie:

type MyType = MyOtherType Int (Bool, [Float])

If you think this is an important feature to support, I'll think harder about it.

[VictorCMiraldo]

I also ran into this in the wild;

VictorCMiraldo/hdiff@e64146f

I'd like to tackle this for this 2.2 version unifying with sop-core

[serras]

Note that the th-abstraction package (which I mentioned in #56) has a function which does exactly what you need: resolveTypeSynonyms. You can even use it without buying the whole library, since the function works on Template Haskell Types.

[VictorCMiraldo]

@serras That seems like a lovely library; I have just tried implementing our Generics.MRSOP.TH module with it this morning but dind't really work for us for two main reasons, explained below.

tl;dr

A naive impl based on th-abstraction won't work. I will think a bit harder about it

Reason 1

All the generation is based on our own datatype:

data DTI var = ADT Name ... [CI var] | New Name ... (CI var)
data CI var = NormalConstr ... | RecordConstr ...

And the beauty of it is that the type pipeline is as follows:

1. reify, then simplify a type to our internal language: sty <- simpl <$> reify name, here sty :: STy.
2. Register sty in a datatbase, assigning it an index.
3. Flatten the topmost type applications, yielding head , args :: (STy , [STy]). For example,
   if sty == Maybe Int in (1), we will have head == Maybe and args == [Int].
4. Now we reify the definition of head in (3) and beta-reduce with the arguments in args.
   This yields a DTI STy, in the maybe case would be something in the lines of: Datatype "Maybe" [Int] [Constr "Just" [simpl Int] , Constr "Nothing"] :: DTI STy
5. We now mapM over this DTI STy with a function keepGoing :: STy -> Writer [STy] IK, where
   we tell the types we have not yet registered, and need to recurse on them, but return
   a DTI IK, which is already exactly the code we need. (data IK = I Int | K Name)

Once we reach a fixpoint of the process above, we end up with a [DTI IK], with self-contained indexes. This makes the generation of the codes very easy. Using th-abstraction we have this
monstrous DatatypeInfo type with all sorts of info we don't need.

Reason 2

The resolveTypeSynonyms is very aggresive. For example, It resolves all occurencs of String
to [Char], which makes the engine detecting that String is supposed to be an opaque type
fail. I'm yet unsure on how to get around that!

[VictorCMiraldo]

I believe I found a decent hack for it in 7c8cdab

Type synonyms seem to be working when generating codes.
Before type synonyms, we kept the following state through the generation:

data Idxs 
  = Idxs { idxsNext :: Int
         , idxsMap  :: M.Map STy (Int , Maybe (DTI IK))
         }
  deriving (Show)

I have added an explicit "this type is equivalent to this" in there:

data Idxs 
  = Idxs { idxsNext :: Int
         , idxsMap  :: M.Map STy (Int , Maybe (DTI IK))
         , idxsSyns :: M.Map STy STy
         }
  deriving (Show)

Now, every time we see a type synonym we exand, reduce and register as equivalent,
as it can be seen here