[darcs-devel] Generic instances for FLs

[Benjamin Franksen]

Am 27.06.19 um 11:17 schrieb Ben Franksen:
> I think the best we can do here is to adopt the hack that the standard
> libraries use for Show a => Show [a]. That is, we add a method
> 'mergeFLFL' to class Merge and then use that as the definition of merge
> in the instance Merge p => Merge (FL p). Then we can define 'mergeFLFL =
> merge2FL' if we have an instance Ident, and use the previous generic
> definition otherwise. (BTW: the generic mergeFL function that merges a
> single patch with an FL is also dangerous as it is now; it should be
> redefined to use mergeFLFL.)

I found out how to select the more efficient (or correct)
implementation, based on whether we have an instance Ident or not. This
gets us rid of the class IdEq2 and re-gains a common interface for many
functions that involve sequences and that make sense for patches with
and without identity, allowing us to scrap things like fastRemoveFL etc.

First we define a class Sequence (if you have a better name, come
forward) to abstract over functions that can be improved with an Ident
instance, as already indicated above:

class (Commute p, Eq2 p) => Sequence p where
  eqForkFL :: FL p wA wB -> FL p wA wC -> EqCheck wB wC -- (=\/=) for FL
  eqJoinFL :: FL p wA wC -> FL p wB wC -> EqCheck wA wB -- (=/\=) for FL
  removeFL :: p wA wB -> FL p wA wC -> Maybe (FL p wB wC)

  eqForkRL :: RL p wA wB -> RL p wA wC -> EqCheck wB wC
  eqJoinRL :: RL p wA wC -> RL p wB wC -> EqCheck wA wB
  removeRL :: p wB wC -> RL p wA wC -> Maybe (RL p wA wB)

(Can add more methods whenever we think this is needed)

We supply default implementations for all methods by copying them from
Darcs.Patch.Permutations.

The generic Eq2 (FL p) instance is re-written as

instance Sequence p => Eq2 (FL p) where
  unsafeCompare = error "Buggy use of unsafeCompare on FL"
  (=\/=) = eqForkFL
  (=/\=) = eqJoinFL

The trick to replace the default definitions with ones that make use of
Ident is to use GeneralizedNewtypeDeriving and DerivingVia which is
available since ghc >= 8.6.

First define a newtype to capture existence of Ident instance:

newtype HasIdent p wX wY = HasIdent (p wX wY) deriving (Commute, Eq2, Ident)

(We could also call this one "ByName" as in 'equate/merge by name'.)

We define /one/ instance of Sequence, namely for this newtype:

instance (Commute p, Eq2 p, Ident p) => Sequence (HasIdent p) where
  eqForkFL ps qs
    | S.fromList (mapFL ident ps) == S.fromList (mapFL ident qs) =
unsafeCoercePEnd IsEq
    | otherwise = NotEq
  -- ...
  removeFL = fastRemoveFL
  -- ...

Now, in the module that implements the patch type, say in
Darcs.Patch.Named, we just need to add

data Named wX wY = ...
  deriving Sequence via (HasIdent (Named p))

and every use of =\/= or removeFL for FLs of Named patches gets the
optimized implementation.

I think the same trick can be played to select the correct merge
implementation.

Cheers
Ben