functional-programming - 在 F# 中更新/多个/更改（有点）二叉树的功能/合理方法

问题描述

=========

我在哪里

我目前正在编写一个我以前用 C# 编写的（非常）小游戏。总的来说，我在 F# 和函数式编程方面没有太多经验，因为我在今年夏末或多或少地偶然发现了它。否则，我至少有几年的一般编程经验和对“比基本更高级”的概念和模式的理解。

游戏逻辑

好吧。我先给你看一张图。

在这个游戏中，玩家将在地图上放置“节点”并将它们连接起来，如上图所示。一些节点（标记为 IN*）将“输出”一个常数值，而其他节点（ADD 和 MULT）将接受两个输入并产生一个输出，例如中间节点接受 5 和 9 并将它们相加，输出 14。

*有比“IN”更好的名字建议吗？它们将始终代表数字 0<n<10。这些数字有英文名称吗？（在瑞典语中是“ental”、“one-numbers”）

如图所示，玩家还可以将一个节点的输出连接到多个（无限）节点。一个节点甚至可以将其输出连接到另一个节点的两个输入。因此，“（有点）二叉树”（这可能有名字吗？）。节点永远无法连接以产生循环，因此如果 A 输出到 B，则 B 不能输出到 A。

重要的是，这种结构可以随时以任何方式发生变化。不能保证所有节点都连接到一个公共根。可能存在多个“树”，然后可以随时连接。

先前的解决方案（oop）

当我之前在 C# 中解决了这个问题时，我有一个节点对象列表。所有节点对象都有两个可能的输入和一个输出。当我更新这个时，我想我寻找没有输出的节点来确定所有根。然后我，在当前节点的输入上递归调用类似.GetValue()或的东西.Update()，然后对其输入执行相同的操作，依此类推。虽然并不完美，这要归功于这种“（有点）二叉树”结构，但它确实有效。

问题/主要问题

我将如何在 F# 中以更实用的方式实现这一点？我认为我需要一个列表，至少更接近 UI，但由于我不认为类之类的引用类型是“功能方式”，我宁愿为每个节点使用 Records。我知道我理论上可以将引用节点的 ID 存储在节点的输入字段中。这似乎有点不安全和笨重，因为没有任何东西（据我所知）可以保证存储的 ID 实际匹配现有节点，并且所有节点的 ID 都是唯一的。

我不认为（至少不容易）我可以存储其他节点的副本而不是 ID，因为节点将具有定义其行为的一流函数，并且据我所知，它们无法进行相等性比较.

是否有任何既定的功能方法来处理这种结构，或者是否有另一种更好的方法来解决这个问题？我已经考虑过存储连接，但我认为这不会有任何帮助。

当然，我非常感谢任何帮助和建议！如果我试图解决错误的问题，请告诉我！谢谢！

标签： functional-programmingf#binary-tree

从这个问题看来，所要求的似乎是所谓的直接无环图。

这是分布式计算中的一种常见模式，并用于 AirFlow、Luigi、Spark 和 Dataflows 等工具。

树非常适合使用，但并非所有问题都可以表示为树。在 FP 中使用图表有点糟糕。有向无环图是中间的东西，可以很好地使用。

下面是在 F# 中表示 DAG 的简单方法。我认为对于问题中概述的场景来说这太简单了，但也许它可以帮助@Evil_Bengt 朝着正确的方向发展。

module FsDag =
  type ReducerOperation = Add|Multiply

  type DAG =
    // Input is a DAG node containing constant input
    | Input   of int
    // Reducer DAG nodes aggregates a list of DAG inputs
    //  using a reducer operation. Reducer is a common expression
    //  for operations that operates on collections and produce value.
    //  Common reducer functions are List.reduce, List.fold and List.sum
    | Reducer of ReducerOperation*DAG list

  // "Constructor" functions for DAG nodes
  let input     i         = Input   i
  let reducer   rop dags  = Reducer (rop, dags)
  let add           dags  = reducer Add      dags
  let multiply      dags  = reducer Multiply dags

  // Evals a DAG into an int value
  let rec eval n =
    match n with
    | Input   i             -> i
    | Reducer (op, sources) ->
      let r, z =
        match op with
        | Add       -> ( + ), 0
        | Multiply  -> ( * ), 1
      sources |> List.map eval |> List.fold r z

open FsDag

[<EntryPoint>]
let main argv =
  let i0 = input 5
  let i1 = input 9
  let dag = multiply [(add [i0; i1]); i1]

  printfn "DAG  %A" dag
  printfn "Eval %A" (eval dag)
  0