开发者

F# Group or aggregate a record sequence/collection by a given criteria

I am pretty new to functional programming and therefore F# and I have serious trouble to come up with the right solution for this problem.

I have got a sequence of record types, say like:

type Invoice = {
    GrpText : string
    GrpRef : int
    Article : int
    Wkz : int
    Text : string
    Price : decimal
    InvoiceRef : int
}

Now I want to group or aggregate the sequence of Invoices by a given criteria and i.e. sum their prices. Invoices that does not match the criteria should not be grouped and just returned as they are.

A criteria function might look like this:

/// determines whether to group the two given Invoice items or not
let criteria item toCompareWith =
    (item.Gr开发者_StackOverflowpRef > 0 && item.Article = toCompareWith.Article
        && item.InvoiceRef = toCompareWith.InvoiceRef) ||
    (item.Wkz <> 0 && item.Text = toCompareWith.Text)

The aggregation or grouping could look like this:

/// aggregate the given Invoice items
let combineInvoices item1 item2 =
    {item1 with Price = item1.Price + item2.Price; Wkz = 0}

The problem looks kind of simple but I am currently not experienced enough in functional programming to connect the dots.

Edit:

I just modified the criteria function in order to better show that it might be a bit more complex than grouping by one or multiple fields.


Unless I'm missing something, there are two steps involved: group and reduce. The easiest way to group is Seq.groupBy. Since you want to use custom equality you need to either apply the [<CustomEquality>] attribute to your type and override Equals and GetHashCode, or roll your own key generating function that uses your concept of equality. Here's an example of the latter.

//custom key generator
let genKeyWith compare =
  let lookup = ResizeArray()
  fun item ->
    match Seq.tryFindIndex (compare item) lookup with
    | Some idx -> idx
    | None ->
      lookup.Add(item)
      lookup.Count - 1

Usage

let getKey = genKeyWith criteria

let invoices = Seq.init 10 (fun _ -> Unchecked.defaultof<Invoice>)

invoices 
|> Seq.groupBy getKey
|> Seq.map (fun (_, items) -> Seq.reduce combineInvoices items)


Something like this where Defaultinvoice is some sort of '0' invoice

input 
|> Seq.groupBy (fun t -> t.Article) 
|> Seq.map (fun (a,b) -> a, (b |> List.fold (fun (c,d) -> combineInvoices c d) Defaultinvoice)

EDIT - For more complicated combine function.

So if your combine function is more complicated, the best approach is probably to use recursion and I think it is going to be hard to avoid a O(n^2) solution. I would go with something like

let rec overallfunc input =
    let rec func input (valid:ResizeArray<_>) =
        match input with
        |[] -> valid //return list
        |h::t -> 
            match valid.tryfindIndex (fun elem -> criteria h elem) with //see if we can combine with something
            |Some(index) -> valid.[index] <- combineInvoices (valid.[index]) h //very non-functional here
            |None -> valid.Add(h)
            func t valid //recurse here
    func input (ResizeArray<_>())

This solution is both highly non-functional and probably very slow, but it should work for arbitrarily complicated combination functions

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜