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) |> 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?