How can this functional implementation of Kadane's algorithm be improved?

Question

Some time ago I posted on Stack Overflow an imperative C# implementation of Kadane's algorithm for finding a subarray with maximum sum. Then I considered implementing the same functionally in F# and came up with the following:

let kadanes (xs: int []) =
    xs
    |> Array.mapi (fun i x -> (x, i))
    |> Array.fold (fun (partSum, partIdx, maxSum, startIdx, endIdx) (x, i) ->
                        let newPartSum, newPartIdx =
                            if partSum + x > x then (partSum + x, partIdx) else (x, i)
                        if newPartSum > maxSum then
                            (newPartSum, newPartIdx, newPartSum, newPartIdx, i)
                        else (newPartSum, newPartIdx, maxSum, startIdx, endIdx))
                        (0,0,xs.[0],0,0)
    |> fun (_, _, maxSum, startIdx, endIdx) -> (maxSum, startIdx, endIdx)

While the implementation above is functional and correct I cannot consider it easily understandable; in particular, dragging tuple of 5 elements through the fold seems rather ugly.

What can be done for improving this F# code?

Thank you.

Answer 1

A recursive function often works well in place of fold.

let kadanes xs =
  let rec loop (partSum, partIdx, maxSum, startIdx, endIdx) i =
    if i < Array.length xs then 
      let x = xs.[i]
      let newPartSum, newPartIdx =
        if partSum + x > x then (partSum + x, partIdx) else (x, i)
      let maxSum, startIdx, endIdx =
        if newPartSum > maxSum then (newPartSum, newPartIdx, i)
        else (maxSum, startIdx, endIdx)
      loop (newPartSum, newPartIdx, maxSum, startIdx, endIdx) (i + 1)
    else (maxSum, startIdx, endIdx)
  loop (0,0,xs.[0],0,0) 0

Answer 2

Although Daniel's suggestion is sound and appreciated, the idiomatic improvement direction is more likely to be from a recursive function to a fold, not vice versa. Staying with fold I tried the following:

• make more apparent the fold arguments by moving the initial accumulator in front of input array and them arguments through ||>
• make factors defining the outcome of folding step in the body of folder function more noticeable by first disassembling accumulator into logical groups, and then reassembling it back with the help of in.

Here is the improved code:

let kadanes (xs: int[]) =
    ((0,0,xs.[0],0,0), (xs |> Array.mapi (fun i x -> (x, i))))
    ||> Array.fold (fun (partSum, partIdx, maxSum, startIdx, endIdx) (x, i) ->
                    let (newPartSum, newPartIdx) = if partSum + x > x then (partSum + x, partIdx) else (x, i) in
                    let (newMaxSum, newStartIdx, newEndIdx) = if newPartSum > maxSum then (newPartSum, newPartIdx, i) else (maxSum, startIdx, endIdx) in
                    (newPartSum, newPartIdx, newMaxSum, newStartIdx, newEndIdx))
    |> fun (_, _, maxSum, startIdx, endIdx) -> (maxSum, startIdx, endIdx)