I am unsure about this change, which is why I am not screening it.

Do we gain anything here, performance-wise, at least theoretically?

Or do we perhaps loose some laziness?

1 patch for repository http://darcs.net/screened:

patch f00b09c351bd5e3b841fdd51c603eaaf70e2a7a4
Author: Ben Franksen <ben.franksen@online.de>
Date:   Mon Jul  3 09:06:38 CEST 2023
  * make partitionRL properly tail recursive

  If we use accumulating parameters anyway, we should go all the way and add
  as many as it takes.

Attachments

• make-partitionrl-properly-tail-recursive.dpatch
• patch-preview.txt

I never intuitively know what tail-recursiveness really means in a lazy
language, though I think there are descriptions online.

From a quick glance without thinking very deeply, I doubt we lose any
laziness because the existing code already does a case analysis
on the recursive call to go before returning anything.

We end up doing another pass for reverseFL anyway, so unless it's more
efficient to do that pass via the accumulating parameters (in both
go and reverseFL) than on the stack, I'd guess there's no performance
difference either.

For the record, this is what we get if we make the opposite move i.e.
towards constructor-guarded "lazy" recursion. The code is modelled directly
after the implementation of 'partition' in base. Things to note:

* The "natural" fold for RL is foldl, not foldr.

* The commutation is done in the "condition does not hold" case.

* The lazy pattern match in the definition of select is out-commented,
  otherwise we get the infamous "An existential or GADT data constructor
  cannot be used inside a lazy (~) pattern". To fix that we'd have to do an
  unsafe coercion.

1 patch for repository http://darcs.net/screened:

patch 167462ca6bafb51b08ddd0168f4892b39e1fc7b7
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Aug 29 11:55:37 CEST 2023
  * make partitionRL "lazy" (not really)

Attachments

• make-partitionrl-_lazy_-_not-really_.dpatch
• patch-preview.txt

If we do want to invest significant effort in this I'd suggest
writing some unit tests that also test laziness behaviour. (Or
maybe there already are some, I didn't check.)

No, that was just for illustration. I think we should accept that 
laziness is not achievable here. Most of the interesting functions 
need at least some amount of commutation to take place and therefore 
trying to make them lazy is hopeless simply because commutation can 
fail.

If anything, I would re-write them in a fully tail-recursive manner, 
adding as many accumulating parameters as needed. This means we can 
assume that these functions are fully strict in the sense that pattern 
matching on the outer-most constructor of the result will evaluate it 
completely. At least this makes reasoning about performance easier.

I would then change return types so that we can remove any final 
reverseFL/RL, as I have already done for some of the functions in 
D.P.Permutations. This opens opportunities for client code to optimize 
it away (either because we need the other direction anyway or because 
we can use the mixed append operators +>>+ or +<<+).

And yes, unit tests would come in handy if we ever want to do this 
systematically.

I've marked the ticket as "in-discussion".