Accumulator and head value generics are swapped for hlist `foldl` and `foldr`

[ImmemorConsultrixContrarie]

It was especially irksome when I was writing #170, since you can't use the same generic poly for both folds:

struct Sum;
impl<Acc, T> Func<(Acc, T)> for Sum
where
    Acc: std::ops::Add<T, Output = Acc>
{
    type Output = Acc;

    fn call(args: (Acc, T)) -> Acc {
        args.0 + args.1
    }
}

Now you can only use this with foldl. You can't even implement Func<(T, Acc)> for Sum, 'cuz generics; a whole new struct SumR is needed to use foldr. It is not so bad with a single closure, though you can't use the same closure for both and have to do argument reverse:

let rfolder = |t, init| lfolder(init, t);

So, was this a deliberate choice? Or would you accept a PR that reverses T, Init into Init, T for all right folds?

[ExpHP]

I would think it must be deliberate, as this definition of a right fold is consistent with many functional languages. I took a look at the list at the table of languages at https://en.wikipedia.org/wiki/Fold_(higher-order_function) and surveyed those languages I could find with dedicated functionality for a right fold:

• Accumulator on right: Haskell, F#, Kotlin, Lisp, OCaml
• Accumulator on left: Javascript (Edit: also rust apparently!!!)

Putting it on the right is in line with this interpretation of a right fold as a means of recursively applying a binary operator #:

 left fold:  ((((a # b) # c) # d) # e)
right fold:  (a # (b # (c # (d # e))))

[lloydmeta]

Yeah, this was a deliberate choice as per @ExpHP. and TIL that JS puts the acc on the left..

Now, that doesn't mean that we shouldn't consider reversing it; after all, on a practical level @ImmemorConsultrixContrarie (what a name btw!) has highlighted the advantage of making this more reusable.

On the other hand, it would be a breaking change, and it might be surprising, given cross-language convention...

[ImmemorConsultrixContrarie]

cross-language convention

It's not really cross-language, more like FP-cross-language convention. It's not even Rust-convenient: DoubleEndedIterator::rfold generics have the exactly same definitions as Iterator::fold generics.

Still a breaking change for anyone who used foldr, though frunk is not 1.0 yet, and even then it is possible to go 2.0, 'cuz frunk is not stdlib.

Though I think pros of this change outweigh a con of breaking a code that used foldr:

1. Being Rust-convenient.
2. If you want to use foldr instead of foldl you change one letter and it just works.

Eh, that's it for pros, but really, the second point is just so DRY.

[ImmemorConsultrixContrarie]

change one letter and it just works

Okay, it's "change one letter and it just works for everything except single-fn-folds", due to reference to Fn in foldr. Though, foldr with single Fn could take unreferenced Fn with some dirty hacks:

impl<F, R, H, Tail, Init> HFoldRightable<F, Init> for HCons<H, Tail>
where
    Tail: fn_foldr::FnHFoldRightable<F, Init>,
    F: Fn(H, <Tail as HFoldRightable<F, Init>>::Output) -> R,
{
    type Output = R;

    fn foldr(self, folder: F, init: Init) -> Self::Output {
        fn_foldr::FnHFoldRightable::real_foldr(self, folder, init).0
    }
}

mod fn_foldr {
    use super::{HCons, HFoldRightable, HNil};

    #[doc(hidden)]
    pub trait FnHFoldRightable<Folder, Init>: HFoldRightable<Folder, Init> {
        fn real_foldr(self, folder: Folder, init: Init) -> (Self::Output, Folder);
    }

    #[doc(hidden)]
    impl<F, Init> FnHFoldRightable<F, Init> for HNil {
        fn real_foldr(self, f: F, i: Init) -> (Self::Output, F) {
            (i, f)
        }
    }

    #[doc(hidden)]
    impl<F, H, Tail, Init> FnHFoldRightable<F, Init> for HCons<H, Tail>
    where
        Self: HFoldRightable<F, Init>,
        Tail: FnHFoldRightable<F, Init>,
        F: Fn(H, <Tail as HFoldRightable<F, Init>>::Output) -> Self::Output,
    {
        fn real_foldr(self, folder: F, init: Init) -> (Self::Output, F) {
            let (folded_tail, folder) = self.tail.real_foldr(folder, init);
            ((folder)(self.head, folded_tail), folder)
        }
    }
}

[ExpHP]

I actually had no idea rust had an rfold. And since 1.27, even...!

That's certainly a large argument in favor of changing foldr. I'll need to rethink my stance a bit.

Eh, that's it for pros, but really, the second point is just so DRY.

Honestly, to me, though, this is actually the part of the problem. What's the point in even having foldr if it was identical to .into_reverse().fold()? (the latter is orthogonal, which IMO is even better than simply being DRY)

(alternatively, one could say that the extra boilerplate required to implement foldr in frunk is potentially saving the user from some boilerplate when dealing with a right-associative function like exponentiation..... though off-hand I can't think of any realistic use cases for HLists)

[lloydmeta]

IMO, there aren't that many practical arguments against doing this; the FnHFoldRightable leak into the implementation of HFoldRightable is a bit of a shame, but 🤷🏼‍♂️ I think we'll live (or add some docs explaining why it's there)?

My questions at this point would be:

1. Given https://github.com/lloydmeta/frunk/issues/171#issuecomment-812454214 are there any other gotchas to it actually making life easier in real life for users (beyond the implementation)? I guess we would need to do the changes and update examples to see?
2. Do we want to do this before or after #170?

[ImmemorConsultrixContrarie]

1. That's mostly about lifetimes in generic bounds, not about allowing the user to swap fold type without adding/removing a single &:

H: HFoldLeftable<Acc, F> <=> H: HFoldRightable<Acc, F>
vs
H: HFoldLeftable<Acc, F> <=> H: for <'a> HFoldRightable<Acc, &'a F>

Also, if you would (once upon a time) replace Fn bound with FnMut in folds, it would be like this for both folds:

f: Fn <=> mut f: FnMut
vs
f: Fn <=> mut f: FnMut <- foldl
f: &'a Fn <=> f: &'a mut FnMut <- foldr

Anyway, I'm probably not the best feedback source here, because if I need a homogeneous list it would be a vector, an array, or a mix of those two types. At the very least those types could be iterated with loops instead of recursion.

2. After merging #170; this way there would be much less rebases (at least for me). Also, if you would push a library version after #170, it would be a minor version update; PR that closes this issue would be a major version update.