How to write a Serialize instance for this GADT?

Question

Below is a module that attempts to implement a Serialize instance for a simple GADT. Unfortunately the get implementation for the Reorder constructor complains that there is no Ixed a constraint. Is there any way, beautiful or ugly, to implement this? I can't add Ixed a to the instance context because the Update constructor needs to work for values that don't satisfy this constraint.

{-# LANGUAGE GADTs #-}

import Control.Lens (Index, Ixed)
import Data.Serialize

-- | Two different ways of updating a value - replacing it completely or,
-- if it is an instance of Ixed, re-ordering it.
data Op a where
  Update :: Serialize a => a -> Op a
  Reorder :: (Ixed a, Serialize (Index a)) => [Index a] -> Op a

instance Serialize a => Serialize (Op a) where
  put (Update a) = putWord8 1 >> put a
  put (Reorder ks) = putWord8 2 >> put ks
  get = do
    i <- getWord8
    case i of
      1 -> Update <$> get
      2 -> Reorder <$> get
      _ -> error "instance Serialize (Op a) - corrupt data"

Addendum: One simplification to this might be to make the type variable a a phantom type, so that Op looks like this:

data Op a where
  Update :: Serialize a => ByteString -> Op a
  Reorder :: (Ixed a, Serialize (Index a)) => [ByteString] -> Op a

The type could then be used to properly decode the byte strings. Not sure whether this helps

I realize Ixed does not imply a total ordering of elements, my real instance has additional constraints. — David Fox
I assume Op a is going to be part of some larger recursive structure, and you want to serialize BiggerThing a containing lots of Op as at types a both with and without Ixed a, right? — K. A. Buhr
This looks tricky to handle. Ideally, we should somehow serialize the Ixed dictionary together with the data, but that might be very hard and result in a very inefficient, very redundant serialization format. As a partial fix, one might add to that instance a custom class constraint such as class IsIxed a where isIxed :: Maybe (Dict (Ixed a)), and then populate this class with "enough" types, covering "enough" cases to make the serialization useful. Or, perhaps, even Typeable a so that we can handle a small number of "known good" cases. Not an ideal solution. — chi
K. A. Buhr - Yes, I need to serialize larger structures containing these. — David Fox
I'm not seeing that making Op a GADT is helping. Why not two different datatypes Update, Reorder with two different instances of Serialize? — AntC

DDub DDub · Accepted Answer · 2021-01-29T02:04:55

What you're trying to do is impossible in general. Essentially, you're trying to get GHC to deduce Ixed a and Serialize (Index a) given only Serialize a. Granted, this may work for any use case you have in mind, but it doesn't generally work, which is why GHC is rejecting your instance.

I said "impossible in general" because if you specify the types you care about, then it's definitely possible. This means you'll have to list out all the types you have that can be serialized from Reorder, but that's really as good as you're going to get.

There are multiple ways to do this, but I think the simplest way is to use the constraints package to capture what you want in a Dict. You'd start by defining:

class MaybeSerializeIndexed a where
  canSerializeIndex :: Maybe (Dict (Ixed a, Serialize (Index a)))
  default canSerializeIndex :: (Ixed a, Serialize (Index a)) -> Maybe (Dict (Ixed a, Serialize (Index a)))
  canSerializeIndex = Just Dict

The default signature (which requires the DefaultSignatures pragma) is key to making your life simple as it means that you can list out the types you care about with easy one liners, as in:

instance Serialize a => MaybeSerializeIndexed [a]
instance Serialize k => MaybeSerializeIndexed (Map k a)

Beyond that, you can make an overlapping instance to deal with the types that don't work with Reorder:

instance {-# OVERLAPPABLE #-} MaybeSerializeIndexed a where
  canSerializeIndex = Nothing

With this machinery in place, you can write your instance:

instance (MaybeSerializeIndexed a, Serialize a) => Serialize (Op a) where
  put (Update a) = putWord8 1 >> put a
  put (Reorder ks) = putWord8 2 >> put ks
  get = do
    i <- getWord8
    case (i, canSerializeIndex @a) of
      (1, _)         -> Update <$> get
      (2, Just Dict) -> Reorder <$> get
      _ -> error "instance Serialize (Op a) - corrupt data"

Note that adding the MaybeSerializeIndexed a constraint to your instance is really not a big deal because there is an instance for every type. This also means that if you add a new type to your system without adding an MaybeSerializeIndexed instance for it, then you won't get a type error when you try to deserialize it—you'll only get a runtime error. For example, if you add a new type Foo where you know Ixed Foo and Serialize (Index Foo) but you don't add instance MaybeSerializeIndexed Foo, then you won't get a type error if you write a program that tries to get a Foo value, but you will get a runtime error when you run it.

How to write a Serialize instance for this GADT?

2 Answers