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.