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
精彩评论