递归记录定义中的匿名泛型参数

Question

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

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

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

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

因为我并不关心SubState list是什么类型，但是它出错了:

声明中不允许使用匿名类型变量

是否有一种不同的、更习惯的f#方法来做到这一点，或者我必须采用另一种解决方案?

Answer 1

Tomas是对的，在f#中没有超级干净的方法来做到这一点，但我认为有可能比他的方法做得更好。基本的想法是你想要一个这样的类型:

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 []}]
}

Answer 2

这在f#中并没有一个很好的解决方案。在实践中，我可能只保留状态为obj，并将其打开为我期望的类型，或者使用捕获可能情况的简单判别联合来存储状态。

有一个非常复杂的方法来做到这一点，这可能是编码你想要的，但会使你的代码看起来相当可怕(我玩这个，我不认为我可以使它很好)。这个想法是用一个单一的Invoke泛型方法存储接口，该方法将使用存储在子类中的类型的类型参数进行调用:

type InvokeWithState<'R> =
  abstract Invoke<'T> : State<'T, 'R> list -> 'R
and State<'T, 'R> =
  { CurrentNodeId : int
    Data : 'T
    SubStates : InvokeWithState<'R> -> 'R }

所以，如果你想在State<'T, 'R>上做一些操作，你可以写InvokeWithState<'R>接口来处理孩子们的事情。一个简单的HFSM，其根状态包含字符串，子状态包含数字，如下所示:

let hfsm = 
  { CurrentNodeId = 1
    Data = "root"
    SubStates = fun op ->
      op.Invoke
        [ { CurrentNodeId = 2 
            Data = 42
            SubStates = fun op -> op.Invoke [] } ] }

这个想法是SubStates函数将调用Invoke操作并给它State<int, 'R>的值('R类型表示我们正在运行的操作的结果)。

处理这些东西也相当难看——因为普通的f#递归函数不能用另一个类型形参作为实参来调用自己。但是你可以这样写(计算FSM的深度):

type HfsmOp<'R> =
  abstract Invoke<'T> : State<'T,'R> -> 'R
let rec depth =
  { new HfsmOp<int> with
      member x.Invoke(state) =
        let childDepth = 
          { new InvokeWithState<int> with
              member x.Invoke<'T>(states:State<'T, int> list) : int = 
                if List.isEmpty states then 0
                else states |> List.map (fun s -> depth.Invoke<'T> s) |> List.max }
          |> state.SubStates 
        childDepth + 1}
depth.Invoke hfsm

这可能是你想要的(通常)，但它看起来很可怕，我不建议这样做。我们在Deedle的一个地方使用了类似的技巧，但这在范围上非常有限，所以它不会使整个代码库变得丑陋。但在大多数情况下，我会使用歧视联合或obj。