On Fri, Oct 01, 2021 at 10:05:30AM +0100, Tom Ellis wrote:
But performance may differ radically, and `toList` may diverge for `snocList` when infinite on the left, though that's a rather pathological example.
If one can't write Foldable-generic functionality in a way that provides some reasonable uniformity of performance over different instances then one wonders what is point of having Foldable as a typeclass at all. At that point it's just name overloading.
This is why I was reluctant originally to say anything about right-biased structures... They break established expectations. I focused mostly on symmetric structures, for which left and right folds should perform identically (if instances properly take advantage of the symmetry), these are I think practical. About right-biased structures I said: https://dnssec-stats.ant.isi.edu/~viktor/haskell/docs/libraries/base/Data-Fo... Finally, in some less common structures (e.g. snoc lists) right to left iterations are cheaper than left to right. Such structures are poor candidates for a Foldable instance, and are perhaps best handled via their type-specific interfaces. If nevertheless a Foldable instance is provided, the material in the sections that follow applies to these also, by replacing each method with one with the opposite associativity (when available) and switching the order of arguments in the fold's operator. Concrete suggestions to address any issues in this section (now that the title is no longer "Chirality") are welcome (MR 6555). https://gitlab.haskell.org/ghc/ghc/-/merge_requests/6555 -- Viktor.