f# - 递归记录定义中的匿名通用参数

Question

我正在构建 HFSM 并使用记录来跟踪状态:

type State<'a> =
    {
        CurrentNodeId : int
        Data : 'a
    }

当当前节点有另一个 HFSM 作为其一部分时，我也需要跟踪该状态。所以我想做这样的事情

type State<'a> =
    {
        CurrentNodeId : int
        Data : 'a
        SubState : State<_> list
    }

因为我真的不在乎 SubState list 是什么类型，但它会出错:

Anonymous type variables are not permitted in this declaration

是否有不同的、更惯用的 F# 方法来执行此操作，或者我是否必须采用不同的解决方案？

Answer 1

Tomas 是正确的，在 F# 中没有 super 干净的方法来执行此操作，但我认为可以比他的方法做得更好。基本思想是你想要这样的类型:

type State<'a> = {
    CurrentNodeId : int
    Data : 'a
    SubState : ∃'x. State<'x> list
}

除了 F# 不直接支持存在类型。事实证明，有一种相当标准的方法可以根据通用类型(F# 支持)对存在类型进行编码:

∃'x.T<'x> ≡ ∀'z.(∀'x.T<'x> -> 'z) -> 'z

不幸的是，这实际上需要两个额外的类型，因为每个通用量化都被编码为唯一类型上的单个泛型方法:

type State<'a> = {
    CurrentNodeId : int
    Data : 'a
    SubStates : SomeStateList
}
and SomeStateList =
    abstract Apply : StateListApplication<'z> -> 'z
and StateListApplication<'z> =
    abstract Apply : State<'x> list -> 'z

请注意，与 Tomas 的解决方案相比，这里有一个额外的类型，但好处是您不必为特定 State 的所有用途 选择单一返回类型。 (Tomas 的编码基本上是将 SomeStateList 类型内联到 State 并将类型参数 'z 提升到过程中的 State 类型。

现在我们希望能够将某种任意类型的状态列表打包为 SomeStateList。 :

let pack states = { new SomeStateList with member __.Apply a = a.Apply states }

我们可以演示如何使用这些类型与 Tomas 的递归 depth 类似的定义。功能。我们希望我们可以写

let rec depth = 1 + s.SubStates |> List.map depth |> List.fold max 0

但是我们需要添加一些额外的语法来创建和应用我们的泛型类型(尽管如果你眯着眼睛，希望核心逻辑仍然很明显):

// Full type annotation necessary here to get inner use to typecheck
let rec depth<'a> (s:State<'a>) : int = 
    1 + s.SubStates.Apply { 
        new StateListApplication<_> with 
            member __.Apply l = l |> List.map depth |> List.fold max 0 
}

创建图形和应用函数非常简单:

depth {
    CurrentNodeId = 1
    Data = "test"
    SubStates = pack [{ CurrentNodeId = 2
                        Data = 1uy
                        SubStates = pack []}]
}