F# 从 CSV 文件加载树结构

Question

我正在尝试学习F#，迄今为止我非常喜欢它。 我正在尝试以F#的思维方式实现一些C#代码，作为练习和学习的练习。

非常抱歉如果此前已经有人回答过了，但我找不到解决所有问题的答案。

我们有一个销售团队结构，其中有销售主管和普通销售人员。主管可能有也可能没有上级主管。

所有销售数据都来自另一个以CSV格式提供的系统。 在读取记录时，我们不知道该销售人员是否有报告。

我似乎不明白如何在F#的不可变世界中加载树形结构。我相信有一种方法。

我们简化的遗留C#代码定义（翻译成英语）。

public class SalesPerson
{
    public int Id { get; set; }
    public SalesPerson Supervisor { get; set; }
    public List<SalesPerson> Reports { get; private set; } = new List<SalesPerson>();
    public PersonalSales double { get; set; }
    public GroupSales double { get; set; }
}

这是代码的简化版本。然而，问题仍然存在：如何加载树？

我想出了以下的F#类型。

type SalesPerson = {
    Id : int
    Supervisor : SalesPerson option
    Reports : List<SalesPerson> option
    PersonalSales : double
    GroupSales : double
}

我甚至不确定这是否是定义类型的F#方式。

我的问题如下：

1. Supervisor指向另一个SalesPerson，且它是不可变的。如果它被新的SalesPerson替换了（因为不可变数据起作用），则引用将中断。
2. Reports是不可变的。我认为我可以使用C#的List<T>，但我不确定这是否是F#的方法。
3. Supervisor的报告记录不遵循Supervisor记录。它们可能在下面的X行中出现，并且不全部在一起。但是，系统确保Supervisor记录始终会在该主管的任何报告记录之前出现。
4. 如何在加载树之后更新GroupSales计算字段。

示例CSV文件如下：

1,,100.00
2,,110.00
3,1,50.00
4,1,75.00
5,2,80.00
6,,92.00

所以：

1 -> 2 reports
2 -> 1 report
3,4,5,6 -> No reports

我非常感谢你能够为这些问题提供任何“帮助”。

谢谢...

- Crazy Spaniard

Answer 1

如果将树形结构拆分为独立的类型，问题就会变得更加容易解决。对于不可变的树，通常的做法是：

let rawData =
    [ 1, None, 100.00
      2, None, 110.00
      3, Some 1, 50.00
      4, Some 1, 75.00
      5, Some 2, 80.00
      6, None, 92.00 ]

let dataMap = rawData |> List.groupBy (fun (_, superId, _) -> superId) |> Map
let getChildrenData personId = dataMap |> Map.tryFind personId |> Option.defaultValue []

type Tree<'a> = { Data: 'a; Children : List<Tree<'a>> }

type SalesPerson = { Id : int; SupervisorId : int option; PersonalSales : double; GroupSales : double }

let salesPersonTree =
    let rec buildNode (id, superId, sales) =
        let children = getChildrenData (Some id) |> List.map buildNode
        let groupSales = (children |> List.sumBy (fun x -> x.Data.GroupSales)) + sales
        { Data = { Id = id; SupervisorId = superId; PersonalSales = sales; GroupSales = groupSales }
          Children = children }

    let topLevelItems = getChildrenData None
    topLevelItems |> List.map buildNode

总之：将数据按父级分组，然后使用递归函数从顶部节点（没有父级的节点）开始建立树。因为我们已经建立了所有后代节点，完成任何给定节点的构建时，我们可以使用后代数据来计算GroupSales。

您无法直接从给定节点访问父节点，但您具有父ID。只要保留原始salesPeople列表，您就可以获取任何给定父ID的完整数据。

拥有通用的Tree类型的优点之一是可以拥有可重复使用的函数（例如map、fold、tryFind），这些函数适用于任何树。

- TheQuickBrownFox

---

太好了...我开始看到你是如何构建这个结构的。然而，我有一个第四点不知道该怎么做。你会怎么做GroupSales？（自己的PersonalSales + 孩子们的PersonalSales）。我想只计算一次，而不是每次我们要求它时都计算。谢谢，David。 - Crazy Spaniard

@CrazySpaniard 这是可能的，因为我们在构建给定节点时可以获得后代节点数据。然而，这意味着要延迟创建记录类型，直到稍后我们可以计算“GroupSales”。这意味着早期会有一些较少的类型安全性（就像我上面所做的那样，更长时间地保持未标记的元组），或者为原始数据创建一个中间类型。 - TheQuickBrownFox

@CrazySpaniard 我猜你的意思是 GroupSales = PersonalSales + 子代的 GroupSales，这相当于 PersonalSales + 后代 的 PersonalSales。 - TheQuickBrownFox

你的假设完全正确。我的英语在这里有点小问题 ;) （children vs descendants）GroupSales = PersonalSales + 孩子们的GroupSales非常好用。 - Crazy Spaniard

Answer 2

@TheQuickBrownFox 在建模您的领域方面做得很好。

type Employee = { Id : int; SupervisorId : int option; PersonalSales : double }

使用记录/类来表示 Tree 是一种面向对象的处理方式，对于没有很多函数式编程经验的人来说可能更容易理解。

我想向您展示一种更加函数式的方法。

type 'a Tree =
  | Leaf of 'a
  | Branch of 'a * 'a Tree list

Leaf节点是层次结构末端的SalesPerson。而Supervisor及其所有下属都由Branch表示，并一直向上延伸。

type SalesMember =
  | SalesPerson of Employee
  | Supervisor of Employee * SalesMember List

一个 树(Tree) 也会有一个根节点 -- 只能有一个 -- 您可以轻松编写一个函数将 rawData 转换为以下内容:

let rawData =
    [ 0, None, 0.0
      1, Some 0, 100.00
      2, Some 0, 110.00
      3, Some 1, 50.00
      4, Some 1, 75.00
      5, Some 2, 80.00
      6, Some 0, 92.00 ]

let flatList =
    rawData
    |> List.map (fun (id, superId, sales) -> 
                     {Id = id; SupervisorId = superId; PersonalSales = sales})

let getTree salesPeople =
    // To do : validate root
    let root = salesPeople |> List.find (fun p -> p.SupervisorId = None)
    let children supervisorId = 
        salesPeople |> List.filter (fun p -> p.SupervisorId = Some supervisorId)

    let rec loop employee = 
      match children employee.Id with
      | [] -> SalesPerson employee
      | list -> Supervisor (employee, List.map loop list)

    loop root

let salesForce = getTree flatList 

为了实现GroupSales，您可以扩展Supervisor。

type SalesMember =
  | SalesPerson of emp : Employee
  | Supervisor of emp : Employee * reports : List<SalesMember> * groupSales : double

构建此树的一种方法是通过从getTree函数转换树。处理、转换和优化树是一个广泛的主题，for fun and profit总是一个好的起点。

更新 - GroupSales

为了保持简单，我将只使用一个“判别联合”，在第一次运行时将GroupSales设置为零。但是，您可以轻松地调整代码以转换为另一种类型的Tree。

type Employee = { Id : int; SupervisorId : int option; PersonalSales : double }

type GroupSales = double
type SalesMember =
  | SalesPerson of Employee
  | Supervisor of Employee * SalesMember List * GroupSales

let rawData =
    [ 0, None, 0.
      1, Some 0, 100.00
      2, Some 0, 110.00
      3, Some 1, 50.00
      4, Some 1, 75.00
      5, Some 2, 80.00
      6, Some 0, 92.00 ]

let flatList =
    rawData
    |> List.map (fun (id, superId, sales) -> 
                     {Id = id; SupervisorId = superId; PersonalSales = sales})

let getTree salesPeople =
    let root = salesPeople |> List.find (fun p -> p.SupervisorId = None)
    let children supervisorId = 
        salesPeople |> List.filter (fun p -> p.SupervisorId = Some supervisorId)

    let rec loop employee = 
        match children employee.Id with
          | [] -> SalesPerson employee
          | list -> Supervisor (employee, List.map loop list, 0.)

    loop root

let transformTree root =
    let rec getGroupSales = function
      | SalesPerson emp 
        -> emp.PersonalSales
      | Supervisor (sup, reports, _) 
        -> sup.PersonalSales + List.sumBy getGroupSales reports

    let rec loop = function
      | Supervisor (sup, reports, _) as mem
        -> Supervisor (sup, List.map loop reports, getGroupSales mem)
      | salesPerson -> salesPerson

    loop root

let salesForce = 
    flatList 
    |> getTree
    |> transformTree

一种不那么天真的实现方式是将 / calc GroupSales 自底向上转换，这样您就可以使用已经计算出来的 GroupSales。

- Funk

---

我曾经在像这样的树中使用过Leaf/Branch DUs（Discriminated Unions），但我想知道是否有必要。如果一个节点有一个空的子列表，那么它就是一个叶子节点。这也打开了无效状态的可能性：您可以创建一个带有空列表的分支。我认为DU方法在您有固定数量的子节点时是有意义的，例如二叉树。 - TheQuickBrownFox

我认为使用DU而不是记录在功能上并没有更多或更少的作用。 - TheQuickBrownFox

@TheQuickBrownFox 我相信有所不同，函数式语言都是关于类型（和处理它们的函数）。在你的设计中，SalesPerson和Supervisor之间没有区别。考虑一下，如果你发现groupSales字段更适合放在Supervisor级别上，因为他/她拥有这个组。那么你如何实现这一点，而不必也装饰SalesPerson呢？ - Funk

我刚才谈到的是您的“Tree”，而不是您的“SalesMember”，在这里我接受它作为一个有意义的标签更有意义。函数式语言甚至不需要静态类型 :) 我认为DUs是一种很棒的类型系统特性，恰好在静态类型的函数式语言中非常流行。 - TheQuickBrownFox

@Funk 我会认真学习这个新方案的 ;) 似乎他们说的用FP需要“重新连接”你的大脑是真的... 哈哈哈... 非常感谢。 - Crazy Spaniard