2009-11-27 65 views
10

我们在这里开始发霉。我已经在数据的具体表示上测试了一堆树同步代码,现在我需要将它抽象出来,以便它可以与任何支持正确方法的源和目标一起运行。 [实际上,这将是Documentum,SQL层次结构和文件系统等来源;与目标像Solr和自定义的SQL交叉引用存储。]强制仿制药和接口上的F#类型推断保持宽松

棘手的部分是,当我递归一个类型为T的树并同步到一个类型为U的树,在某些文件我需要做在当前节点处将第二类型V与该类型U进行“子同步”。 (V代表分层结构里面的一个文件...)并且F#中的类型推断引擎正在驱动着我,在我尝试将子同步添加到V后,

我代表这个在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电话

,并与()替换它们,那么推论保持通用的,一切都是可爱的。

这是一个相当难题。我试过将第二块中的“比较”函数移出该类型,并将它们定义为递归函数;我试过了一百万种注释或强制输入的方式。我只是不明白!

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

谢谢,如果你读了这么久!啧!

+0

注意:我不太了解静态解析类型参数的用例,比如^ a - 也许碰巧是其中之一? – 2009-11-27 15:58:39

回答

16

我还没有分析的代码足以找出原因,但添加

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. 从上到下,从左到右开始读取方法体(在遇到这种情况时,您会遇到一些可能涉及未解决的类型变量的“前向引用”,这会导致麻烦,因为.. )
  4. 同时解决所有成员机构(...但我们还没有做过任何'概括',但是,那么'推断类型参数'而不是'修正'理论上的部分可能是'a'是它的第一个调用位置所使用的任何具体类型的函数)
  5. 概括(任何剩余的未解析的类型变量变为实际推断的类型变量的通用方法)

这可能不完全正确;我不太了解这个算法,我只是对它有所了解。你可以随时阅读语言规范。

经常发生的事情是,直到第3项和强制推理器开始试图同时解决/约束所有方法体,而实际上它是不必要的,因为例如,也许某些功能具有简单的具体固定类型。像SyncStep是unit-> unit,但F#在第3步中还不知道,因为签名不是显式的,它只是说好的SyncStep的类型为“unit - >'a”,对于某些尚未解析的类型'a和那么现在SyncStep现在通过引入不必要的变量而不必要地使所有解决方案复杂化。

我发现的方式是,第一个警告(这个构造导致代码不如类型注释所指示的通用类型,类型变量'a被限制为类型'V')在最后一行在调用docTree.Compare()时UpdateRenditions的主体。现在我知道Compare()应该是unit - > unit。那么我怎么可能会得到关于通用性那里的警告?啊,好吧,编译器不知道返回类型是在那一点上的单位,所以一定是通用的东西不是。实际上,我可以将返回类型注释添加到比较中而不是SyncStep - 任何一种都可以。

无论如何,我很啰嗦。综上所述

  • 如果你有一个良好的类型的程序,应该“工作”
  • 有时推理算法的细节将需要一些“额外”的注释...在最糟糕的情况下,您可以'全部添加',然后'通过使用编译器警告和推理算法的一些智力模型'删除不必要的'
  • ,您可以快速转向带缺失注释的体验
  • 很多时候,'修复'只是为一些'宣称迟'但'早叫'的关键方法添加一个完整类型签名(包括返回类型)

希望有帮助!

+0

好的。 我在这里换气过度。布莱恩,你真是太棒了。我欠你一杯啤酒。其实这一点我可能欠你晚餐和电影。 Sheeeeesh。 但我有一个问题:如何检查你的病? 哈哈。我想我试着用各种不同的方式强行注释每一个其他功能,但我从来没有想过单元 - >单元功能会从注释中受益。 – 2009-11-27 16:45:31

+3

是的,测试通过了模拟提供商和所有东西。现在我只需要窃取你的大脑。 – 2009-11-27 16:47:16

+0

好吧,我添加了很多的答案,建议你可以用来帮助你下一次的策略:) – Brian 2009-11-27 17:12:07

3

这是一篇旧帖子,但它是我搜索的#1结果。我有一些补充,可以帮助其他任何与我(和OP)有类型推断斗争的人。

我发现它有助于将推理看作函数调用结构的某些指数函数,这些调用可能具有哪些签名以及它们可能没有的签名。考虑到所有三者是非常重要的。

只是踢,考虑这个功能有三个变量:的sqrt(2 * 2 * 3)

向右走,很明显,这将简化到2倍的一些无理数,它必须是圆的(从而获取无限的不精密度)使其在日常生活中有用。

F#版本反馈到它自己,混合错误,直到“四舍五入”最终导致不合意的类型推断。因为类型可能会或可能不会是这个等式中的一个因素,所以直接用类型注释来解决问题并不总是可行的。

现在,假设添加额外的完全通用的(即,中性的)两个问题的功能之间的功能,改变我们的方程这样:SQRT(2 * 2 * 4)

突然,结果是完全合理的,从而产生一个完全准确的值4.相比之下,将反向相关的第一个和第二个值修改为1将完全没有帮助我们。

不要害怕修改结构,如果它有可能造成或破坏整个程序。一个额外的功能与所有必须跳过的(不断地)将F#弯曲成您的意愿的额外功能相比,是一个非常小的代价,您可以找到一种方法来使额外的结构变得有用。在某些情况下,执行上述操作可以将非常非常非常有争议的程序变成一个完美的小天使,以实现许多功能。