# Folding with non zero value

Is it unsafe to use `foldLeft` with a value which is not really the zero value of the underlying monoïd? Here is an example. I have a tail recursive function which calls a function named `relax` to accumulate a change to the given object, `dp` while avoiding mutating. I.e., `relax` might return the given `dp` or an updated object of the same type depending on its internal computation. And I want to do this for every element in the given list of `edges`.

This pattern happens to match the `foldLeft` algorithm, except that in absolutely no way is the initial value of `dp` a zero. It, `dp` is simply the value to return if the list is empty. And if the list is `List(edge)` then the value returned should be `relax(edge,dp)`, and if the list is `List(edge1,edge2)`, then the return value should be either `relax(edge1,relax(edge2,dp))` or `relax(edge2,relax(edge1,dp))`, and I don’t care which, etc for any length.

Below are two implementations of `relaxRemainingEdges` which I believe do the same thing. Is this a misuse of `foldLeft`?

I realize that in the implementation using `foldLeft` the function is really misnamed. The unfortunate name was chosen based on its recursive implementation.

``````def relaxRemainingEdges(edges:List[Edge[A]], dp: DP): DP = {
edges match {
case Nil => dp
case edge :: rest => relaxRemainingEdges(rest, relax(edge, dp))
}
}
def relaxRemainingEdges(edges:List[Edge[A]], dp: DP): DP = {
edges.foldLeft(dp){(dp:DP,edge:Edge[A]) => relax(edge,dp)}
}
``````

By the way, this is the stop of the BellmanFord algorithm which is repeated a precalculated number of times. I’m just trying to write it using immutable data structures.

A `foldLeft` does not require an underlying monoid, otherwise it would not accept a function taking two different types. So your start value doesn’t have to be a neutral element.

Note the difference in the documentation of the parameter `z` for `foldLeft` vs `fold`: in `foldLeft`, it is simply described as “start value”, while `fold` explicitly requires it to be a neutral element and also only accepts functions of type `(A,A) => A`, which have to be associative. The reason is that folding with a monoid allows nondeterministic order, for example by parallelizing the fold.

`foldLeft` and `foldRight` have a deterministic order, which is even included in their name. So I would not see starting with a non-zero value as a misuse.

2 Likes

BTW, regarding the different kinds of folding. I will soon need a 4th fold option. What I call tree-fold. But perhaps there’s a more standard name. E.g., suppose you want calculate products of bignums, which you know are all small. You want to delay the growth as long as possible. So to perform the following

`a * b * c * d * e * f * g ...`

you’d like to fold it this way

`(((a * b) * (c * d)) * ((e * f) * (g * h))) * ...`

and when it fails to be an exact power of 2 number of numbers to multiply, slurp up the remaining ones in any ole way. Because there’s certain to be less than log2(n) of them.

This order of multiplication tends to minimize the number of large multiplications.

It is not too difficult to implement this for `List[A]`, or `Set[A]`, but I don’t know how to implement it as generally as `foldLeft` and `foldRight` are implemented.