Creating a structured category list in F#

Question

This takes a list of categories and organizes them into a tree-type structure based on their parentId. This code works, but is obviously a little over-complicated. How can I optimize it?

type ValidString = | ValidString of string | NotValid
type CategoryStructure = {
 Id: ValidString;
 ParentId: ValidString;
 Name: ValidString;
 Abbreviation: ValidString;
 Description: ValidString;
 SapId: ValidString;
 Section: ValidString;
 SectionPosition: ValidString
}
type DynamicCategories = {
 Category: CategoryStructure;
 SubCategories: seq<DynamicCategories>
}
let rec private structureCategories (fullList: CategoryStructure list) 
 (list: CategoryStructure list) =
 List.fold (fun acc elem -> 
 // get all categories and details
 let categories = fullList
 let mainAcc =
 [
 for row in categories do
 if row = elem
 then
 let subs = 
 List.fold (fun acc' elem' ->
 if row.Id = elem'.ParentStructureId
 then
 let modifiedList = elem' :: List.empty<CategoryStructure>
 let foundSubCategory = 
 {
 Category = elem';
 SubCategories = structureCategories fullList modifiedList |> Seq.ofList
 }
 foundSubCategory :: acc'
 else acc'
 ) List.empty<DynamicCategories> categories
 |> Seq.ofList 
 yield{
 Category = elem;
 SubCategories = subs
 }
 ]
 mainAcc @ acc
 ) List.empty<DynamicCategories> list
// get the initial parent categories and then call the above code to finish the organizing the list
let getStructuredCategories () =
 let categories = allCategoriesAndDetails () |> List.ofSeq
 [
 for row in categories do
 if row.ParentStructureId = NotValid
 then yield row
 ] |> structureCategories categories |> Seq.ofList

• John Palmer: why not use Seq.fold instead of List.fold |> Seq.ofList?
• user1206480: What's the added benefit here for seq.fold. I'm new to f# so there is no particular strategy here other than to just get it initially working. That's why I'm here now, to see how to make this more efficient.
• John Palmer: Its more that your just mixing Lists and Seqs and its not clear why.
• John Palmer: In general, it seems like you do lots of conversions between List and Seq. For example the last function could be let ...() = let t = allcateogriesanddetails(); t |> List.Filter (fun t -> t.ParentStructureID=NotValid) |> StructureCategories categories

Answer 1

Here is an optimized version that I have discovered:

let getStructuredCategories () =
let fullList = allCategoriesAndDetails () 
let parentList () =
 allCategoriesAndDetails ()
 |> Seq.filter (fun p -> p.ParentStructureId = NotValid)
let rec toTree (fullList': seq<CategoryStructure>) (parent: CategoryStructure) =
 fullList'
 |> Seq.filter (fun x -> x.ParentStructureId = parent.Id)
 |> Seq.map (fun x -> 
 {
 Category = x;
 SubCategories =
 toTree fullList' x
 })
seq {
 for row in parentList () do
 yield {
 Category = row;
 SubCategories = toTree fullList row 
 }
}

Can someone else do better?

• John Palmer: The last seq can be replaced with parentList() |> Seq.map (fun t -> Category=t;SubCategories=toTree fillList row
• John Palmer: filter |> map can be replaced by choose