Menu
I'm aware that fold-left produces left-leaning trees and fold-right produces right-leaning trees, but when I reach for a fold, I sometimes find myself getting bogged down in headache-inducing thought trying to determine which kind of fold is appropriate. I usually end up unwinding the entire problem and stepping through the implementation of the fold function as it applies to my problem.
So what I want to know is:
There is an example in Scala by Example (PDF) of using a fold to write a function called flatten which concatenates a list of element lists into a single list. In that case, a right fold is the proper choice (given the way the lists are concatenated), but I had to think about it a bit to arrive at that conclusion.
Since folding is such a common action in (functional) programming, I'd like to be able to make these kinds of decisions quickly and confidently. So... any tips?
936
foldLeft() method is a member of TraversableOnce trait, it is used to collapse elements of collections. It navigates elements from Left to Right order. It is primarily used in recursive functions and prevents stack overflow exceptions.
The foldRight method takes an associative binary operator function as parameter and will use it to collapse elements from the collection. The order for traversing the elements in the collection is from right to left and hence the name foldRight. The foldRight method allows you to also specify an initial value.
A right fold need to cons the last element to the accumulator before consing the second last all the way to the first. This means a right fold should be avoided if possible and in many cases where the order of the result or you fold down to a single value (eg. finding max element) a left fold is ok.
foldRight and reduceRight are in fact tail recursive for Array. It's basically converted into a foldLeft where the index varies in the other direction.
You can transfer a fold into an infix operator notation (writing in between):
This example fold using the accumulator function x
fold x [A, B, C, D] thus equals
A x B x C x D Now you just have to reason about the associativity of your operator (by putting parentheses!).
If you have a left-associative operator, you'll set the parentheses like this
((A x B) x C) x D Here, you use a left fold. Example (haskell-style pseudocode)
foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative If your operator is right-associative (right fold), the parentheses would be set like this:
A x (B x (C x D)) Example: Cons-Operator
foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3] In general, arithmetic operators (most operators) are left-associative, so foldl is more widespread. But in the other cases, infix notation + parentheses is quite useful.
198
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
