Menu
I was looking at the way fold is defined for immutable.Set:
def fold [A1 >: A] (z: A1)(op: (A1, A1) ⇒ A1): A1
yet foldLeft is defined as:
def foldLeft [B] (z: B)(op: (B, A) ⇒ B): B
This looks weird for me, at least at first glance, since I was expecting fold to be able to change the type of the collection it returned, much like foldLeft does.
I imagine this is because foldLeft and foldRight guarantee something about the order in which the elements are folded. What is the guarantee given by fold?
266
The fold method takes two sets of arguments. One contains a start value and the other a combining function. It then steps through the list, recursively applying the function to two operands: an accumulated value and the next element in the list.
The foldLeft 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 left to right and hence the name foldLeft. The foldLeft method allows you to also specify an initial value.
Fold and reduce The difference between the two functions is that fold() takes an initial value and uses it as the accumulated value on the first step, whereas the first step of reduce() uses the first and the second elements as operation arguments on the first step.
Both methods recursively combine items into another item. foldLeft combines items from left one to right one, on the other hand foldRight does this from right one to left one.
When you're applying foldLeft then your start value is combined with the first list element. The result is combined with the second list element. This result with the third and so on. Eventually, the list has collapsed to one element of the same type than your start value. Therefore you just need some type that can be combined by your function with a list element.
For foldRight the same applies but in reverse order.
fold does not guarantee the order in with the combinations are done. And it does not guarantee that it starts off at only one position. The folds might happen in parallel. Because you could have the parallelism it is required that any 2 list elements or return values can be combined – this adds a constraint to the types.
Regarding your comment that you have to see a case were order has an effect: Assume you're using folds to concatenate a list of characters and you want to have a text as result. If your input is A, B, C, you probably would like to preserve the order to receive ABC instead of ACB (for example).
On the other hand if you're, say, just adding up numbers, the order does not matter. Summing up 1, 2, 3 gives 6 independent of the additions' order. In such cases using fold instead of foldLeft or foldRight could lead to faster execution.
112
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
