3
\$\begingroup\$

I am writing a piece of code that returns all the unique variants that a product is available in for an ecommerce app. For example, a shirt product can be available in different colors, sizes, and linen. If the available attributes are red, green, L, XL, Cotton, and Polyester, then a list of the unique variants should be eventually returned as:

[{red; L; Cotton} ; {red; L; Polyester} ; {red; XL; Cotton} ; {red; XL; Polyester} ; {green; L; Cotton} ; {green; XL; Cotton} ; {green; L; Polyester} ;

{green; XL; Polyester}]

This would be the unique variants available for the product.

The code below works and eventually returns a string list of IDs representing each variant available for the product. The only problem that I am having with this is that it generates a duplicate of each variant. I can easily take care of that with a Set.ofList function after this code runs, but would like to solve that problem here internally. I'm new to F#, so what can I do to optimize this code?

type NewProductAttributeInfo = {
    AttributeId : string;
    AttributeCategoryId : string
}


let rec private returnVariant (curIdx: int) (listLength: int) 
    (attList: (int * NewProductAttributeInfo * NewProductAttributeInfo) list) 
    (curList: NewProductAttributeInfo list) =

    match curList with
    | x when x.Length = listLength -> curList
    | x -> 
        let attTup =
            attList
            |> List.filter (fun x' -> 
                                let idx1,att1,att2' = x'
                                idx1 >= curIdx && not(curList 
                                                        |> List.exists (fun x'' -> 
                                                                            x'' = att2'))
                            )
        let idx1,att1,att2 = attTup |> List.head
        let newList = curList @ [att2]
        returnVariant idx1 newList.Length attList newList


let rec calculateVariants (attList: NewProductAttributeInfo list) 
    (currentList: (int * NewProductAttributeInfo * NewProductAttributeInfo) list) =

    // group attribute list by category id
    let attGrouped = attList |> List.groupBy (fun x -> x.AttributeCategoryId)
    let (firstGroupCatId,firstGroupDetails) = attGrouped.[0]




    match currentList with
    | [] ->
        let rawVariants = [for nxt in 0 .. (attGrouped.Length - 1) do
                            if nxt > 0
                            then
                                // begin iteration
                                for d in firstGroupDetails do
                                    let _,det = attGrouped.[nxt]
                                    for det' in det do
                                        yield (nxt, d, det')
                        ]
        calculateVariants attList rawVariants
    | x ->
        let groupLength = x |> List.groupBy (fun (idx,d0,nxtD) -> idx)
                        |> List.length |> ((+)1)
        let sortedGroup = x |> List.sortBy (fun (x,y,z) -> x)
        if groupLength > 2
        then // below is the block that generates the duplicates
            [for att in sortedGroup do
                for attCompare in sortedGroup do
                    let idx1,att1,att2 = att
                    let idx2,attC1,attC2 = attCompare
                    if idx2 > idx1 && att2 <> attC2
                    then
                        let idString = 
                            returnVariant idx2 groupLength x [att1; att2; attC2]
                            |> List.map (fun nl -> nl.AttributeId)
                        yield String.concat "," idString
            ]
        else
            [
                for att in sortedGroup do
                    let idx1,att1,att2 = att
                    let idString = 
                            returnVariant idx1 groupLength x [att1; att2]
                            |> List.map (fun nl -> nl.AttributeId)
                    yield String.concat "," idString
            ]
\$\endgroup\$
6
\$\begingroup\$

If I understand correctly, you're looking for the Cartesian product of the attributes in each attribute category.

To get the Cartesian product, I've adapted* Eric Lippert's solution from his blog post Computing a Cartesian product with LINQ.

let cartesianProduct xs =
    Seq.fold (fun acc xs -> seq {
        for accSeq in acc do
        for x in xs do
        yield Seq.append accSeq (Seq.singleton x)
    }) (Seq.singleton Seq.empty) xs

Then we need to group by the attribute category, and pull out just the attributes**.

let variants (attributes : seq<NewProductAttributeInfo>) =
    attributes
        |> Seq.groupBy (fun attribute -> attribute.AttributeCategoryId)
        |> Seq.map (snd >> Seq.map (fun attribute -> attribute.AttributeId))
        |> cartesianProduct

Here is a test on the sample data you provided

let attributes = [
    { AttributeId = "red"; AttributeCategoryId = "Color" };
    { AttributeId = "L"; AttributeCategoryId = "Size" };
    { AttributeId = "XL"; AttributeCategoryId = "Size" };
    { AttributeId = "Cotton"; AttributeCategoryId = "Material" };
    { AttributeId = "green"; AttributeCategoryId = "Color" };
    { AttributeId = "Polyester"; AttributeCategoryId = "Material" }
]

for variant in variants attributes do
    printfn "%A" variant

Which gives:

seq ["red"; "L"; "Cotton"]
seq ["red"; "L"; "Polyester"]
seq ["red"; "XL"; "Cotton"]
seq ["red"; "XL"; "Polyester"]
seq ["green"; "L"; "Cotton"]
seq ["green"; "L"; "Polyester"]
seq ["green"; "XL"; "Cotton"]
seq ["green"; "XL"; "Polyester"]

* Hopefully without introducing errors.

** This is a little bit nicer in C# since we have the overload of GroupBy that takes an elementSelector parameter:

return attributes.GroupBy(attribute => attribute.CategoryId, attribute => attribute.Id)
    .CartesianProduct();
\$\endgroup\$
  • 2
    \$\begingroup\$ What I don't like about this is that the way you're building the result using Seq.append will be inefficient if you have large number of categories. If you're willing to limit yourself to list instead of seq, you could improve that by using foldBack instead of fold and x::accSeq instead of Seq.append accSeq (Seq.singleton x) (and also modifying the rest of the code accordingly). \$\endgroup\$ – svick Nov 10 '15 at 11:40
  • \$\begingroup\$ @svick good point, thanks for the feedback. \$\endgroup\$ – mjolka Nov 10 '15 at 12:05
  • \$\begingroup\$ @svick can we see an implementation using the list sugestion by @mjolka? \$\endgroup\$ – user1206480 Nov 10 '15 at 15:04
3
\$\begingroup\$

As requested, this is a modification of mjolka's answer to use list instead of seq. Originally, I assumed this is going to be more efficient, because enumerating Seq.append accSeq (Seq.singleton x) would be \$O(n^2)\$ (just like Enumerable.Concat(accSeq, new[] { x })).

But if I understand the source of Seq.append correctly, it's actually smart enough to stay \$O(n)\$, so my modification is not likely to bring much benefit.

let cartesianProduct xs =
    List.foldBack (fun xs acc -> [
        for accSeq in acc do
        for x in xs do
        yield x::accSeq
    ]) xs [[]]

let variants (attributes : list<NewProductAttributeInfo>) =
    attributes
        |> List.groupBy (fun attribute -> attribute.AttributeCategoryId)
        |> List.map (snd >> List.map (fun attribute -> attribute.AttributeId))
        |> cartesianProduct
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.