-
Notifications
You must be signed in to change notification settings - Fork 57
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Accumulator and head value generics are swapped for hlist foldl
and foldr
#171
Comments
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:
Putting it on the right is in line with this interpretation of a right fold as a means of recursively applying a binary operator
|
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... |
It's not really cross-language, more like FP-cross-language convention. It's not even Rust-convenient: Still a breaking change for anyone who used Though I think pros of this change outweigh a con of breaking a code that used
Eh, that's it for pros, but really, the second point is just so DRY. |
Okay, it's "change one letter and it just works for everything except single-fn-folds", due to reference to 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)
}
}
} |
I actually had no idea rust had an That's certainly a large argument in favor of changing foldr. I'll need to rethink my stance a bit.
Honestly, to me, though, this is actually the part of the problem. What's the point in even having (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) |
IMO, there aren't that many practical arguments against doing this; the My questions at this point would be:
|
Also, if you would (once upon a time) replace
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.
|
It was especially irksome when I was writing #170, since you can't use the same generic poly for both folds:
Now you can only use this with
foldl
.You can't even implement
Func<(T, Acc)> for Sum
, 'cuz generics; a whole newstruct SumR
is needed to usefoldr
.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:
So, was this a deliberate choice? Or would you accept a PR that reverses
T, Init
intoInit, T
for all right folds?The text was updated successfully, but these errors were encountered: