F# idiomatic Seq/List Look ahead and modification?

Question

Is there an idiomatic way in F# to look ahead in a list/seq/array and use the information learned in the processing of the current item? In my scenario it would also be necessary to mutate (or otherwise store the fact it was changed) the ahead item so it is processed correctly in turn. I'm implementing some rather silly business rules and such a pattern or technique would be useful.

Right now I'm using an accumulator to store the information and then mutating items of an array as I process each. This feels a bit clumsy as you can see in the simplified example below. The actual business rules for the problem I'm solving are more complex so I rather not trudge down this path if there is a better way. Essentially, I want to get rid of graceMonths in the Acc type and instead solve those months by looking ahead in the list/seq/array.

The mock example: Workers get some type of bonus when they reach a desired level of production each month. If they fail to meet the desired level they can make up for it by exceeding the level in following months. Likewise, they can bank excess production for use in future months where they fall short. The following script shows an example.

type CalendarMonth = 
    { year : int
      month : int }

type InMonth = 
    { month : CalendarMonth
      prodCount : int }

type OutMonth = 
    { month : CalendarMonth
      prodCount : int
      borrowedFrom : InMonth list
      metProd : bool }

type OutMonthAcc = 
    { outMonth : OutMonth
      notUsed : InMonth list }

type IndexOutMonth = 
    { index : int
      outMonth : OutMonth }

type Acc = 
    { index : int
      graceMonths : IndexOutMonth list
      bankedProd : InMonth list
      arrRef : OutMonth array }

type GraceAcc = 
    { processed : IndexOutMonth list
      notUsed : InMonth list }

let createMonth y m c = 
    { InMonth.month = 
          { year = y
            month = m }
      prodCount = c }

let toOutPutMonth (x : InMonth) = 
    { month = x.month
      prodCount = x.prodCount
      borrowedFrom = []
      metProd = false }

let toSimple (x : OutMonth) = sprintf "year: %i, month: %i, metProd: %b" x.month.year x.month.month x.metProd

let solveWithBanked desiredProd bank m = 
    let useProd (acc : OutMonthAcc) inMonth = 
        let m = acc.outMonth
        if m.metProd then 
            { acc with notUsed = inMonth :: acc.notUsed }
        else 
            let borrowed = m.borrowedFrom |> List.sumBy (fun x -> x.prodCount)
            let needed = desiredProd - (m.prodCount + borrowed)
            match inMonth.prodCount with
            | x when x < needed -> 
                { outMonth = { m with borrowedFrom = inMonth :: m.borrowedFrom }
                  notUsed = acc.notUsed }
            | x when x > needed -> 
                let newInMonth = { inMonth with prodCount = inMonth.prodCount - needed }

                let newOutMonth = 
                    { m with borrowedFrom = newInMonth :: m.borrowedFrom
                             metProd = true }
                { outMonth = newOutMonth
                  notUsed = newInMonth :: acc.notUsed }
            | _ -> 
                { outMonth = 
                      { m with borrowedFrom = inMonth :: m.borrowedFrom
                               metProd = true }
                  notUsed = acc.notUsed }
    bank |> List.fold useProd { outMonth = m
                                notUsed = [] }

let solveGrace desiredProd bank (graceLst : IndexOutMonth list) = 
    let useBank acc iOutMonth = 
        let result = iOutMonth.outMonth |> solveWithBanked desiredProd acc.notUsed
        if result.outMonth.metProd then 
            let iMonth = 
                { index = iOutMonth.index
                  outMonth = result.outMonth }
            { processed = iMonth :: acc.processed
              notUsed = result.notUsed }
        else { acc with processed = iOutMonth :: acc.processed }
    graceLst
    |> List.sortBy (fun x -> x.index)
    |> List.fold useBank { processed = []
                           notUsed = bank }

let solve desiredProd acc m = 
    match m.prodCount < desiredProd with
    | true -> // less
        let result = m |> solveWithBanked desiredProd acc.bankedProd
        if result.outMonth.metProd then 
            acc.arrRef.[acc.index] <- result.outMonth
            { acc with index = acc.index + 1
                       bankedProd = result.notUsed }
        else 
            let iMonth = 
                { IndexOutMonth.index = acc.index
                  outMonth = m }
            { acc with index = acc.index + 1
                       graceMonths = iMonth :: acc.graceMonths }
    | false -> // greater
        let newM = 
            { index = acc.index
              outMonth = { m with metProd = true } }

        let newIn = 
            { InMonth.month = m.month
              prodCount = m.prodCount - desiredProd }

        let result = acc.graceMonths |> solveGrace desiredProd (newIn :: acc.bankedProd)
        let solved, unsolved = result.processed |> List.partition (fun x -> x.outMonth.metProd)
        newM :: solved |> List.iter (fun x -> acc.arrRef.[x.index] <- x.outMonth)
        { acc with index = acc.index + 1
                   graceMonths = unsolved
                   bankedProd = result.notUsed }

let jan = createMonth 2013 01 4
let feb = createMonth 2013 02 4
let mar = createMonth 2013 03 6
let apr = createMonth 2013 04 7
let may = createMonth 2013 05 4
let jun = createMonth 2013 06 4

let arr = 
    jan :: feb :: mar :: apr :: may :: jun :: []
    |> Array.ofList
    |> Array.map toOutPutMonth

arr |> Array.fold (solve 5) { index = 0
                              graceMonths = []
                              bankedProd = []
                              arrRef = arr }

let result = 
    arr
    |> Array.map toSimple
    |> List.ofArray

The value of result should show all months met production except June. Is this the right approach in F# or is there a better way?

Answer 1

This is the approach I would try here:

• Calculate the differences between the expected and actual amounts for each month upfront,
• Split the months into three groups - the ones that are below the quota, above the quota and ones that exactly make the quota,
• Attempt to balance the ones below the quota with the ones above the quota.

The first two points seem pretty self-explanatory to me, as for the third one, here's the draft of the balance function and an example usage:

let (|Lt|Eq|Gt|) (a, b) =
    if a = b 
        then Eq
        elif a > b then Gt else Lt

let rec balance below above balanced = 
    match below, above with
    | (x, required)::xs, (y, available)::ys ->
        match required, available with
        | Lt -> balance xs ((y, available - required) :: ys) (x::balanced)
        | Eq -> balance xs ys (x::y::balanced)
        | Gt -> balance ((x, required - available) :: xs) ys (y::balanced)
    | _, _ -> 
        below, above, balanced

balance [("a", 4); ("b", 1)] [ ("c", 2); ("d", 2) ] [ "e" ]
balance [("a", 1); ("b", 1)] [ ("c", 2); ("d", 2) ] [ "e" ]

Essentially you walk the two lists in parallel, "taking" from the one and "adding" to the other, until you run out of either one. What remains is the best attempt at making things balanced.

Typically you want to use collection APIs like the List module when writing F# code, but it's useful to remember that you can always fall back to "raw" recursion when your use case doesn't seem to fit into existing schemes.