Some time ago I posted on Stack Overflow 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.
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.
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.
How this functional implementation of Kadane's algorithm can be improved?
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.