Folds are not implemented for `&hlist` and `&mut hlist`

[ImmemorConsultrixContrarie]

Reasons to have it

The main reason to have it is performance.

1. Destructing HCons<H, T> into H and T copies both H and T.
2. Destructing &HCons<H, T> into &H and &T involves only pointer arithmetic with constants and one pointer copy.

hlist.to_ref().fold() // create a new hlist with a bunch of pointers, then destruct it.
(&hlist).fold() // pointer arithmetic

The compiler might optimize both lines into the same binary code, or it might not.

Problems

The biggest problem will be UX. Right now HCons and HNil have nice methods foldl and foldr, and to use those methods the user doesn't have to import any traits. With three fold impls for hlist, &hlist and &mut hlist, there should be either no method on the struct itself, or three methods with different names, kinda like into_iter(), iter() and iter_mut().

Also, there will be some inconsistency between folds and other things like HMappable, which will be implemented for by-value hlists only; though HMappable could be implemented with foldr, and the usefulness of this trait is a bit questionable. IntoReverse could be implemented with foldl. ToRef and ToMut could be implemented with foldr.

Problems of not having those impls

Some libraries may use hlist instead of tuples with

impl_trait_for_tuples!(A, B, C, /* … */);

to make compilation time a bit better, or to avoid some unnecessary unsafe in those impls (because hlist could be folded, while tuple could not be).

However, generic bounds without fold impls for &hlist and &mut hlist could be messy (or won't compile at all without some serious thinking):

UserHlist: HFoldLeftable<ByValFolder, ValAcc> + for <'a> ToRef<'a>,
for <'a> <UserHlist as ToRef<'a>>::Output: HFoldLeftable<ByRefFolder, RefAcc>,

Then, the library will write its own HFoldLeftable (or HFoldRightable) due to either performance or generic problems. However, if every such library would write its own folding trait, the user who will try to use both of those libraries in the same function will have to write a bit of boilerplate:

fn foo<H>(h: &H)
where &H: lib1::HFoldLeftable<Folder, Acc> + lib2::HFoldLeftable<Folder, Acc>
{}

The traits are identical, but the user should write both of them in the bound *sad user noises*.

So, yeah, any thoughts about it, @lloydmeta, @ExpHP ?

[ImmemorConsultrixContrarie]

Also, the thing about boilerplate is that it is not just in the generic bounds:

where &H: lib1::HFoldLeftable<Folder, Acc> + lib2::HFoldLeftable<Folder, Acc>

but in the calls to foldl too:

let a1 = lib1::HFoldLeftable::foldl(&hlist);
let a2 = lib2::HFoldLeftable::foldl(&hlist);

You can't just import both traits and call a hlist.foldl() due to trait ambiguity.

Though, this is unlikely to be a problem, because what sane human being will use two identical traits in the same function, right?

[ExpHP]

IIRC way back when I was experimenting with the refactor of frunk, impls of traits on &'a Self with bounds of traits on &'a T used to run into some nasty compiler bugs where, when you used the impls, the compiler would often run into an infinite loop and fail trying to prove something weird like HCons<HCons<HCons<HCons<HCons<HCons<HCons<...>>>>>>>: Sized. I forget the specifics. (This also happened with things like impl Add<U> for &'a NewType<T> where &'a T: Add<U>)

ToRef was kind of a compromise, keeping the refness of the operation orthogonal to the operation itself, similar to Option::as_ref, and dodging all of those silly bugs by making them irrelevant.

The compiler bugs might be fixed now. I think you're free to try adding some of these impls.

[ExpHP]

By the way, I found an old comment showing the sort of thing that used to make the compiler explode: https://github.com/lloydmeta/frunk/pull/106#issuecomment-377927198

[BGR360]

FWIW, I successfully made this work with the new Coproduct::map() method I added.

[ExpHP]

The 1.67 release notes have this:

https://github.com/rust-lang/rust/pull/100386/

I wonder if that fixes the exploding Sized bounds mentioned above?