I've been working on adding support for generic deriving to linear-base, building on some work started by Sjoerd Visscher. Things generally work out about as well as can be expected for performance with generics, but I'm running into an issue with recursive types (like lists) that I don't know what to do about. The simplest example of this is the Consumable class. Don't be thrown by the linear type stuff if you're not familiar with it; it's pretty much irrelevant here. We have
class Consumable a where
-- Read this as consume :: a -> (), but it's guaranteed to use
-- its argument exactly once.
consume :: a %1 -> ()
instance (Generic a, GConsumable (Rep a)) => Consumable (Generically a) where
consume (Generically x) = genericConsume x
genericConsume :: (Generic a, GConsumable (Rep a)) => a %1 -> ()
genericConsume = gconsume . from
{-# INLINEABLE genericConsume #-}
-- | A class for generic representations that can be consumed.
class GConsumable f where
gconsume :: f p %1 -> ()
instance GConsumable U1 where
gconsume U1 = ()
{-# INLINE gconsume #-}
instance (GConsumable f, GConsumable g) => GConsumable (f :+: g) where
gconsume (L1 a) = gconsume a
gconsume (R1 a) = gconsume a
{-# INLINE gconsume #-}
instance (GConsumable f, GConsumable g) => GConsumable (f :*: g) where
gconsume (a :*: b) = gconsume a `seqUnit` gconsume b
{-# INLINE gconsume #-}
instance Consumable c => GConsumable (K1 i c) where
gconsume (K1 c) = consume c
{-# INLINE gconsume #-}
instance GConsumable f => GConsumable (M1 i t f) where
gconsume (M1 a) = gconsume a
{-# INLINE gconsume #-}
-- There are instances for more generic representations, but
-- they're not relevant to the question
If we define
deriving via
Generically [a]
instance
Consumable a => Consumable [a]
then we get the following Core (-ddump-simpl -dsuppress-coercions -dsuppress-type-applications):
Rec {
-- RHS size: {terms: 15, types: 12, coercions: 2, joins: 0/0}
Data.Unrestricted.Linear.Internal.Consumable.$fConsumableNonEmpty_$cconsume1 [Occ=LoopBreaker]
:: forall a. Consumable a => [a] %1 -> ()
[GblId, Arity=2, Str=<LCL(A)><1L>, Unf=OtherCon []]
Data.Unrestricted.Linear.Internal.Consumable.$fConsumableNonEmpty_$cconsume1
= \ (@a_a6VD)
($dConsumable_a6VE :: Consumable a_a6VD)
(eta_B0 :: [a_a6VD]) ->
case eta_B0 of {
[] -> GHC.Tuple.();
: f1_a7mo f2_a7mp ->
case ($dConsumable_a6VE `cast` <Co:2>) f1_a7mo of { () ->
Data.Unrestricted.Linear.Internal.Consumable.$fConsumableNonEmpty_$cconsume1
$dConsumable_a6VE f2_a7mp
}
}
end Rec }
See the problem? This is a loop breaker with no unfolding, so it can't specialize to a particular Consumable a instance. Ugh. Writing the Consumable instance manually, we can avoid this problem with scoped type variables:
instance Consumable a => Consumable [a] where
consume = go
where
go :: [a] %1 -> ()
go [] = ()
go (x : xs) = consume x `seqUnit` go xs
Now we get the much more satisfactory
-- RHS size: {terms: 18, types: 16, coercions: 2, joins: 1/1}
Data.Unrestricted.Linear.Internal.Consumable.$fConsumableNonEmpty_$cconsume1
:: forall a. Consumable a => [a] %1 -> ()
[GblId,
Arity=2,
Str=<LCL(A)><1L>,
Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,
WorkFree=True, Expandable=True,
Guidance=ALWAYS_IF(arity=2,unsat_ok=True,boring_ok=False)
Tmpl= \ (@a_a71g)
($dConsumable_a71h [Occ=OnceL1!] :: Consumable a_a71g)
(eta_B0 [Occ=Once1] :: [a_a71g]) ->
joinrec {
go_s7zZ [Occ=LoopBreakerT[1]] :: [a_a71g] %1 -> ()
[LclId[JoinId(1)], Arity=1, Str=<L>, Unf=OtherCon []]
go_s7zZ (ds_d7bD [Occ=Once1!] :: [a_a71g])
= case ds_d7bD of {
[] -> GHC.Tuple.();
: x_a59q [Occ=Once1] xs_a59r [Occ=Once1] ->
case ($dConsumable_a71h `cast` <Co:2>) x_a59q of { () ->
jump go_s7zZ xs_a59r
}
}; } in
jump go_s7zZ eta_B0}]
Data.Unrestricted.Linear.Internal.Consumable.$fConsumableNonEmpty_$cconsume1
= ....
Is there any way to achieve this with generics, or is that a lost cause?
In principle, GHC could lift out the static dictionary argument(s); perhaps this problem is best addressed at the compiler level?
I just realized that this problem also affects generic deriving for NFData. Ouch!