generics - 强制泛型和接口(interface)上的 F# 类型推断保持宽松

Question

我们这里变得毛茸茸的。我已经在数据的具体表示上测试了一堆树同步代码，现在我需要对其进行抽象，以便它可以与支持正确方法的任何源和目标一起运行。 [实际上，这将是 Documentum、SQL 层次结构和文件系统等来源；具有 Solr 等目的地和自定义 SQL 交叉引用存储。]

棘手的部分是，当我向下递归类型 T 的树并同步到类型 U 的树时，在某些文件中，我需要将第二种类型 V 与该类型 U 进行“子同步”在当前节点。 ( V 表示文件内部的层次结构...)当我尝试将子同步添加到 V 时，F# 中的类型推断引擎就让我在这个问题上兜圈子。

我用 TreeComparison<'a,'b> 来表示它，因此上面的内容会产生 TreeComparison<T,U> 和 TreeComparison<V,U> 的子比较。

问题是，一旦我在其中一个类方法中提供具体的 TreeComparison<V,'b> ，当我希望第一个类型参数保持通用( V )时，when 'a :> ITree 类型就会传播到所有推断。也许我可以对 TreeComparison<V,'b> 值进行一些输入？或者，更有可能的是，这个推论实际上告诉我，我思考这个问题的方式本质上是有问题的。

这确实很难压缩，但我想提供工作代码，您可以将其粘贴到脚本中并进行实验，因此开头有大量类型...如果您愿意，核心内容就在最后跳过。大多数通过 ITree 进行的跨类型的实际比较和递归都被砍掉了，因为没有必要看到我正在努力解决的推理问题。

open System

type TreeState<'a,'b> = //'
  | TreeNew of 'a
  | TreeDeleted of 'b
  | TreeBoth of 'a * 'b

type TreeNodeType = TreeFolder | TreeFile | TreeSection

type ITree =
  abstract NodeType: TreeNodeType
  abstract Path: string
      with get, set

type ITreeProvider<'a when 'a :> ITree> = //'
  abstract Children : 'a -> 'a seq
  abstract StateForPath : string -> 'a

type ITreeWriterProvider<'a when 'a :> ITree> = //'
  inherit ITreeProvider<'a> //'
  abstract Create: ITree -> 'a //'
  // In the real implementation, this supports:
  // abstract AddChild : 'a -> unit
  // abstract ModifyChild : 'a -> unit
  // abstract DeleteChild : 'a -> unit
  // abstract Commit : unit -> unit

/// Comparison varies on two types and takes a provider for the first and a writer provider for the second.
/// Then it synchronizes them. The sync code is added later because some of it is dependent on the concrete types.
type TreeComparison<'a,'b when 'a :> ITree and 'b :> ITree> =
  {
    State: TreeState<'a,'b> //'
    ATree: ITreeProvider<'a> //'
    BTree: ITreeWriterProvider<'b> //'
  }

  static member Create(
                        atree: ITreeProvider<'a>,
                        apath: string,
                        btree: ITreeWriterProvider<'b>,
                        bpath: string) =
      { 
        State = TreeBoth (atree.StateForPath apath, btree.StateForPath bpath)
        ATree = atree
        BTree = btree
      }

  member tree.CreateSubtree<'c when 'c :> ITree>
    (atree: ITreeProvider<'c>, apath: string, bpath: string)
      : TreeComparison<'c,'b> = //'
        TreeComparison.Create(atree, apath, tree.BTree, bpath)

/// Some hyper-simplified state types: imagine each is for a different kind of heirarchal database structure or filesystem
type T( data, path: string ) = class
  let mutable path = path
  let rand = (new Random()).NextDouble
  member x.Data = data
  // In the real implementations, these would fetch the child nodes for this state instance
  member x.Children() = Seq.empty<T>

  interface ITree with
    member tree.NodeType = 
      if rand() > 0.5 then TreeFolder
      else TreeFile
    member tree.Path
      with get() = path
      and set v = path <- v
end

type U(data, path: string) = class
  inherit T(data, path)
  member x.Children() = Seq.empty<U>
end

type V(data, path: string) = class
  inherit T(data, path)
  member x.Children() = Seq.empty<V>
  interface ITree with
    member tree.NodeType = TreeSection
end


// Now some classes to spin up and query for those state types [gross simplification makes these look pretty stupid]
type TProvider() = class
  interface ITreeProvider<T> with
    member this.Children x = x.Children()
    member this.StateForPath path = 
      new T("documentum", path)
end

type UProvider() = class
  interface ITreeProvider<U> with
    member this.Children x = x.Children()
    member this.StateForPath path = 
      new U("solr", path)
  interface ITreeWriterProvider<U> with
    member this.Create t =
      new U("whee", t.Path)
end

type VProvider(startTree: ITree, data: string) = class
  interface ITreeProvider<V> with
    member this.Children x = x.Children()
    member this.StateForPath path = 
      new V(data, path)
end


type TreeComparison<'a,'b when 'a :> ITree and 'b :> ITree> with
  member x.UpdateState (a:'a option) (b:'b option) = 
      { x with State = match a, b with
                        | None, None -> failwith "No state found in either A and B"
                        | Some a, None -> TreeNew a
                        | None, Some b -> TreeDeleted b
                        | Some a, Some b -> TreeBoth(a,b) }

  member x.ACurrent = match x.State with TreeNew a | TreeBoth (a,_) -> Some a | _ -> None
  member x.BCurrent = match x.State with TreeDeleted b | TreeBoth (_,b) -> Some b | _ -> None

  member x.CreateBFromA = 
    match x.ACurrent with
      | Some a -> x.BTree.Create a
      | _ -> failwith "Cannot create B from null A node"

  member x.Compare() =
    // Actual implementation does a bunch of mumbo-jumbo to compare with a custom IComparable wrapper
    //if not (x.ACurrent.Value = x.BCurrent.Value) then
      x.SyncStep()
    // And then some stuff to move the right way in the tree


  member internal tree.UpdateRenditions (source: ITree) (target: ITree) =
    let vp = new VProvider(source, source.Path) :> ITreeProvider<V>
    let docTree = tree.CreateSubtree(vp, source.Path, target.Path)
    docTree.Compare()

  member internal tree.UpdateITree (source: ITree) (target: ITree) =
    if not (source.NodeType = target.NodeType) then failwith "Nodes are incompatible types"
    if not (target.Path = source.Path) then target.Path <- source.Path
    if source.NodeType = TreeFile then tree.UpdateRenditions source target

  member internal tree.SyncStep() =
    match tree.State with
    | TreeNew a     -> 
        let target = tree.CreateBFromA
        tree.UpdateITree a target
        //tree.BTree.AddChild target
    | TreeBoth(a,b) ->
        let target = b
        tree.UpdateITree a target
        //tree.BTree.ModifyChild target
    | TreeDeleted b -> 
        ()
        //tree.BTree.DeleteChild b

  member t.Sync() =
    t.Compare()
    //t.BTree.Commit()


// Now I want to synchronize between a tree of type T and a tree of type U

let pt = new TProvider()
let ut = new UProvider()

let c = TreeComparison.Create(pt, "/start", ut , "/path")
c.Sync()

问题可能与 CreateSubtree 相关。如果您注释掉其中一个:

1. docTree.Compare() 行
2. tree.UpdateITree 调用

并将它们替换为 () ，然后推理保持通用，一切都很可爱。

这真是一个难题。我尝试将第二个 block 中的“比较”函数移出类型并将它们定义为递归函数；我已经尝试过一百万种注释或强制打字的方法。我就是不明白!

我考虑的最后一个解决方案是为子同步的比较类型和函数制作一个完全独立(且重复)的实现。但这是丑陋且可怕的。

感谢您阅读到这里!谢啦!

Answer 1

我还没有对代码进行足够的分析来找出原因，但添加了

  member internal tree.SyncStep() : unit =
                             //   ^^^^^^

似乎已经解决了。

编辑

另请参阅

Why does F# infer this type?

Understanding F# Value Restriction Errors

Unknown need for type annotation or cast

需要经验才能非常深入地了解 F# 类型推理算法的功能和局限性。但这个例子似乎属于人们在做非常高级的事情时遇到的一类问题。对于类的成员，F# 推理算法会执行类似的操作

1. 查看所有成员显式签名，为所有成员设置初始类型环境
2. 对于任何具有完全显式签名的成员，请将其类型固定为显式签名
3. 开始从上到下、从左到右阅读方法主体(执行此操作时，您会遇到一些可能涉及 Unresolved 类型变量的“前向引用”，这可能会导致麻烦，因为......)
4. 同时求解所有成员体(...但我们还没有进行任何“泛化”，这部分将“推断类型参数”而不是“修复”理论上可能是“a 的函数”的部分无论其第一个调用站点使用什么具体类型)
5. 泛化(任何剩余的未解析类型变量都会成为泛型方法的实际推断类型变量)

这可能不完全正确；我不太了解它，无法描述该算法，我只是有一个感觉。您可以随时去阅读语言规范。

经常发生的情况是，您到达第 3 点并迫使推理器开始尝试同时求解/约束所有方法体，而实际上这是不必要的，因为，例如也许某些函数有一个简单的具体固定类型。就像 SyncStep 是 unit->unit，但 F# 在步骤 3 中还不知道它，因为签名不明确，它只是说 ok SyncStep 对于某些尚未解决的类型 'a 具有类型“unit -> 'a”并且那么现在 SyncStep 通过引入不必要的变量使所有求解变得不必要地复杂化。

我发现这一点的方式是，第一个警告(此构造导致代码比类型注释指示的更不通用。类型变量“a 已被限制为类型“V”)位于最后一行调用 docTree.Compare() 时的 UpdateRenditions 主体。现在我知道 Compare() 应该是单位 -> 单位。那么我怎么可能会收到关于通用性的警告呢？啊，好吧，编译器当时并不知道返回类型是单位，所以它必须认为某些东西是通用的，但不是。事实上，我可以将返回类型注释添加到 Compare 而不是 SyncStep - 两者都可以。

不管怎样，我实在是太啰嗦了。总结一下

• 如果您有一个类型良好的程序，它应该“有效”
• 有时推理算法的细节需要一些“额外”注释...在最坏的情况下，您可以“将它们全部添加”，然后“减去不必要的”
• 通过使用编译器警告和推理算法的一些心理模型，您可以凭借经验快速找到缺失的注释
• 通常情况下，“修复”只是向某些“较晚声明”但“较早调用”的关键方法添加一个完整的类型签名(包括返回类型)(在一组成员之间引入前向引用)<

希望有帮助!