How to make Bimap an instance of SafeCopy?

Question

When I recently tried to serialize a data structure in which I used Data.Bimap, I encountered the problem that Bimap is not an instance of SafeCopy.

Now, after having a look in Data.SafeCopy.Instances, I came up with the following:

instance (SafeCopy a, SafeCopy b, Ord a, Ord b) => SafeCopy (Bimap a b) where
    getCopy = contain $ fmap fromAscPairList safeGet
    putCopy = contain . safePut . toAscList

This compiles but I have no idea whether it does the right thing.

Answer 1

The SafeCopy part of your implementation is correct, but there is an issue with the Bimap part. The problem is that toAscList and fromAscPairList have different requirements. In the documentation for bimap the following is stated about these functions:

toAscList:

Convert to a list of associated pairs, with the left-hand values in ascending order.

fromAscPairList:

Build a bimap from a list of pairs, where both the fst and snd halves of the list are in strictly ascending order.

So toAscList will build a list where the left side values are in order, while fromAscPairList requires both values to be in order. So your implementation will cause a runtime-error when you try to deserialize a map where both values don't have the same ordering. Here is an example:

> fromAscPairList $ toAscList $ fromList [(1,3),(2,2)]
fromList *** Exception: Data.Bimap.fromAscPairList: list not correctly ascending

You can fix this issue by replacing toAscList with toList and fromAscPairList with fromList.