(This is forked off of Monad of No Return: Issues with `(>>) = (*>)` - #18 by L0neGamer, since discussing how to optimize common implementations of (*>) isn’t quite on topic there.)
So here’s the Core produced by @effectfully’s example for (*>):
lvl5 = \ @b -> One id
Rec {
$fApplicativeNonEmpty2
= \ @b @a ds ->
case ds of {
One x -> lvl5;
Cons x xs -> Cons id ($fApplicativeNonEmpty2 xs)
}
end Rec }
$fApplicativeNonEmpty_$c*>
= \ @a @b eta eta1 ->
letrec {
go
= \ ds ->
case ds of {
One f2 ->
letrec {
go1
= \ ds1 ->
case ds1 of {
One x -> One (f2 x);
Cons x xs -> Cons (f2 x) (go1 xs)
}; } in
go1 eta1;
Cons f2 fs ->
let { ys = go fs } in
letrec {
go1
= \ ds1 ->
case ds1 of {
One x -> Cons x ys;
Cons x xs -> Cons x (go1 xs)
}; } in
letrec {
go2
= \ ds1 ->
case ds1 of {
One x -> One (f2 x);
Cons x xs -> Cons (f2 x) (go2 xs)
}; } in
go1 (go2 eta1)
}; } in
go ($fApplicativeNonEmpty2 eta)
There’s an opportunity for a case-of-case transformation to be applied to the composition of go and $fApplicativeNonEmpty2, though I expect it isn’t being taken because both of those functions are recursive? But if we inline and apply it by hand, we get this:
$fApplicativeNonEmpty_$c*>
= \ @a @b eta eta1 ->
letrec {
go
= \ ds ->
case ds of {
One f2 ->
letrec {
go1
= \ ds1 ->
case ds1 of {
One x -> One (f2 x);
Cons x xs -> Cons (f2 x) (go1 xs)
}; } in
go1 eta1;
Cons f2 fs ->
let { ys = go fs } in
letrec {
go1
= \ ds1 ->
case ds1 of {
One x -> Cons x ys;
Cons x xs -> Cons x (go1 xs)
}; } in
letrec {
go2
= \ ds1 ->
case ds1 of {
One x -> One (f2 x);
Cons x xs -> Cons (f2 x) (go2 xs)
}; } in
go1 (go2 eta1)
}; } in
case eta of {
One x -> letrec {
go1 -- LOOK HERE
= \ ds1 ->
case ds1 of {
One x1 -> One (id x1);
Cons x1 xs -> Cons (id x1) (go1 xs)
}; } in
go1 eta1;
Cons x xs ->
let { ys = go ($fApplicativeNonEmpty2 xs) } in
letrec {
go1
= \ ds1 ->
case ds1 of {
One x1 -> Cons x1 ys;
Cons x1 xs1 -> Cons x1 (go1 xs1)
}; } in
letrec {
go2
= \ ds1 ->
case ds1 of {
One x1 -> One (id x1);
Cons x1 xs1 -> Cons (id x1) (go2 xs1)
}; } in
go1 (go2 eta1)
}
Then, all we have to do is notice that the go1 marked with -- LOOK HERE is the identity function (unless we are -fpedantic-bottoms). This is again probably an issue because go1 is also recursive, but GHC already does this sort of thing for non-recursive functions.
If we can do those two optimizations, that’s enough for (*>) to be tail-recursive in its second operand if its first is One. Nothing about this is specialized to anything from Functor or Applicative, and no new language features need to be added. GHC just has to try things it already does in the context of non-recursive functions in a recursive context.
I say ‘just’, but, uh, I imagine there are good reasons why this hasn’t been supported yet. How hard would these particular extensions be, folks who know?