How to use seq.groupby and seq.fold to create a tree (F#)?

Question

This fails (can it be done?):

Assume, I have a tree (to be displayed in WPF) as:

type BranchDate = {Id: Guid; PostingDate: DateTime}

type LedgerRecord = {        
        rid: Guid                       
        DebitCredit: string option      
        PostingTime: DateTime option
        BillTo: string option           
        CptCode: string option
        Description: string option
        Charge: double option
        CheckNum: string option
        PaymentMethod: string option     
        Paid: double option
        Refiled: double option           
        EncounterInsuranceId : int option
        CptId: int option
    }

type Tree =
  | Branch of BranchDate * Tree list
  | Leaf of LedgerRecord

The LederRecords are downloaded from a database as seq<LedgerRecords>.

My best effort fails with

 let MakeTree (p:LedgerRecord[] option) : Tree = 


  let insert tree  = raise <| NotImplementedException()


  let makeBranch (d:DateTime) (v:seq<LedgerRecord>) : Tree = 
     Branch ({Id = Guid.NewGuid(); PostingDate = d}, v |> Seq.map (fun q -> Leaf q) |> Seq.toList)

  let root = Branch ( {Id=Guid.NewGuid(); PostingDate = new DateTime(01,01,01)}, [] )
  
  let ggg = 
            match p with
            | None -> failwith "Branch ( {Id=Guid.NewGuid(); PostingDate = new DateTime(01,01,01)}, [] )"
            | Some pp -> pp 
                            |> Seq.groupBy (fun t -> Option.get t.PostingTime)
                            |> Seq.map (fun (k,v) -> makeBranch k v)
   
  let hhh = Seq.fold insert root ggg  
  hhh

I cannot get how to write "insert" that produces the tree. In Wpf, the tree is to be displayed as:

1/1/1919
      shirt
      pants
      shoes
2/3/1956
      carpet
      heater
      dog food

Any help is most appreciated.

TIA

Answer 1

I agree with Konst Sh that a recursive data structure is overkill for this, but here's how it could be done. For clarity, I've simplified your types as follows:

type Record =
    {
        Date : DateOnly
        Name : string
    }

type Tree =
    | Branch of DateOnly * List<Tree>
    | Leaf of Record

Then building trees from records can be done like this:

let makeTrees records =
    records
        |> Seq.groupBy (fun rcd -> rcd.Date)
        |> Seq.sortBy fst
        |> Seq.map (fun (date, group) ->
            let children =
                group
                    |> Seq.map Leaf
                    |> Seq.toList
            Branch (date, children))

Note that fold isn't needed; a simple map suffices instead.

Test case:

let records =
    [
        "2/3/1956", "carpet"
        "1/1/1919", "shirt"
        "2/3/1956", "heater"
        "1/1/1919", "pants"
        "1/1/1919", "shoes"
        "2/3/1956", "dog food"
    ] |> Seq.map (fun (date, name) ->
        { Date = DateOnly.Parse(date); Name = name })

let rec printTree = function
    | Branch (date, children) ->
        printfn $"{date}"
        for child in children do
            printTree child
    | Leaf rcd -> printfn $"   {rcd.Name}"

for tree in makeTrees records do
    printTree tree

Output is:

1/1/1919
   shirt
   pants
   shoes
2/3/1956
   carpet
   heater
   dog food