Clean up constant returns from workers
Motivation
I was playing around writing a safe init
function as a "good consumer":
-- | A safe version of `init`.
-- @safeInit [] = Nothing@
-- @safeInit xs = Just $ init xs@
safeInit :: [a] -> Maybe [a]
safeInit xs = case si xs of
(False, _) -> Nothing
(_, ys) -> Just ys
si :: [a] -> (Bool, [a])
si xs0 = foldr go stop xs0 Nothing
where
stop Nothing = (False, [])
stop _ = (True, [])
go x r Nothing = (True, snd (r (Just x)))
go x r (Just p) = (True, p : snd (r (Just x)))
The compiled code is pretty good. Here's -ddump-simpl
:
Rec {
-- RHS size: {terms: 20, types: 32, coercions: 0, joins: 0/0}
Sinit.safeInit_$spoly_$wgo [Occ=LoopBreaker]
:: forall a. a -> [a] -> (# Bool, [a] #)
[GblId, Arity=2, Caf=NoCafRefs, Str=<L,U><S,1*U>, Unf=OtherCon []]
Sinit.safeInit_$spoly_$wgo
= \ (@ a_a1Jn) (sc_s2WY :: a_a1Jn) (sc1_s2WX :: [a_a1Jn]) ->
case sc1_s2WX of {
[] -> (# GHC.Types.True, GHC.Types.[] @ a_a1Jn #);
: y_a2SL ys_a2SM ->
(# GHC.Types.True,
GHC.Types.:
@ a_a1Jn
sc_s2WY
(case Sinit.safeInit_$spoly_$wgo @ a_a1Jn y_a2SL ys_a2SM of
{ (# ww1_s2W0, ww2_s2W1 #) ->
ww2_s2W1
}) #)
}
end Rec }
-- RHS size: {terms: 14, types: 23, coercions: 0, joins: 0/0}
safeInit :: forall a. [a] -> Maybe [a]
[GblId,
Arity=1,
Caf=NoCafRefs,
Str=<S,1*U>,
Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
WorkFree=True, Expandable=True, Guidance=IF_ARGS [30] 70 30}]
safeInit
= \ (@ a_a1Jn) (xs_aXV :: [a_a1Jn]) ->
case xs_aXV of {
[] -> GHC.Maybe.Nothing @ [a_a1Jn];
: y_a2SL ys_a2SM ->
GHC.Maybe.Just
@ [a_a1Jn]
(case Sinit.safeInit_$spoly_$wgo @ a_a1Jn y_a2SL ys_a2SM of
{ (# ww1_s2W0, ww2_s2W1 #) ->
ww2_s2W1
})
}
-ddump-stg
gives something similar, and I think the relevant situation survives at least to CMM.
This is almost the same as what you'd write by hand. But
- The worker produces an unboxed tuple whose first component is always
True
. - The worker always throws away the first component of the result of the recursive call.
- The wrapper always throws away the first component of the result.
So there's really no use producing this True
at all.
Proposal
I think a couple different approaches could work.
The first approach, which seems a bit more robust, but that doesn't admit an obvious well-localized implementation, would be to notice that the Bool
component of the result is never, ever used, and therefore there's no need for it to exist.
The second approach is to notice that the first component of the result is always the same. That would let us break up the worker in a second round of worker/wrapper:
subWrapper :: forall a. a -> [a] -> (# Bool, [a] #)
subWrapper x xs = case subWorker x xs of
(# ys #) -> (# True, ys #)
subWorker :: forall a. a -> [a] -> (# [a] #)
subWorker x xs = ...
Inlining the subWrapper
into safeInit
would get rid of the extra return.