Patch 2359 make partitionRL properly tail recursive

Title make partitionRL properly tail recursive
Superseder Nosy List bfrk
Related Issues
Status in-discussion Assigned To

Created on 2023-08-24.16:55:36 by bfrk, last changed 2023-08-29.12:14:35 by bfrk.

File name Status Uploaded Type Edit Remove
make-partitionrl-_lazy_-_not-really_.dpatch bfrk, 2023-08-29.10:10:45 application/x-darcs-patch
make-partitionrl-properly-tail-recursive.dpatch bfrk, 2023-08-24.16:55:35 application/x-darcs-patch
patch-preview.txt bfrk, 2023-08-24.16:55:35 text/x-darcs-patch
patch-preview.txt bfrk, 2023-08-29.10:10:42 text/x-darcs-patch
See mailing list archives for discussion on individual patches.
msg23695 (view) Author: bfrk Date: 2023-08-24.16:55:35
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.
msg23707 (view) Author: ganesh Date: 2023-08-28.14:01:40
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.
msg23717 (view) Author: bfrk Date: 2023-08-29.10:10:45
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)
msg23718 (view) Author: ganesh Date: 2023-08-29.10:13:06
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.)
msg23719 (view) Author: bfrk Date: 2023-08-29.12:14:35
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 

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 

I've marked the ticket as "in-discussion".
Date User Action Args
2023-08-24 16:55:36bfrkcreate
2023-08-28 14:01:42ganeshsetmessages: + msg23707
2023-08-29 10:10:47bfrksetfiles: + patch-preview.txt, make-partitionrl-_lazy_-_not-really_.dpatch
messages: + msg23717
2023-08-29 10:13:08ganeshsetmessages: + msg23718
2023-08-29 12:14:35bfrksetstatus: needs-screening -> in-discussion
messages: + msg23719