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.