This one looks a little funky, but counterintuituvely, it's a bunch faster for
nonempty lists.
foldr needs two passes, too. The big win here is that it's extremely easy to
comprehend: flip it, chop off the head, flip it again.
As for why it's faster: as stated, foldr needs two passes. First, it needs to go
to the end of the list, then back to the beginning while applying a function to
every element. In this implementation, we need two passes, too, but we only
apply a single, constant time function between the passes.
Long story short, 70% slower for empty lists (since we still need to call 3
functions), 50% faster for a single element, 300 to 500% improvement for lists
of 10 to 1000 elements.
Chadtech
commented
6 years ago
This one looks a little funky, but counterintuituvely, it's a bunch faster for nonempty lists.
foldrneeds two passes, too. The big win here is that it's extremely easy to comprehend: flip it, chop off the head, flip it again.As for why it's faster: as stated, foldr needs two passes. First, it needs to go to the end of the list, then back to the beginning while applying a function to every element. In this implementation, we need two passes, too, but we only apply a single, constant time function between the passes.
https://ellie-app.com/fFq6s2PcTa1/0 for benchmarks.
Long story short, 70% slower for empty lists (since we still need to call 3 functions), 50% faster for a single element, 300 to 500% improvement for lists of 10 to 1000 elements.