F# 递归类型：方法与函数类型推断差异

Question

有人可以解释一下为什么在 F# 中类型推断似乎在 class 方法和函数之间工作不同（或我不明白的其他方面？）。

假设如下（简化）：

type Node<'T> = Node2 of 'T * 'T
type Digit<'T> = One of 'T | Two of 'T * 'T
type Tree<'T> =
    | Empty
    | Single of 'T
    | Deep of prefix : Digit<'T> * deeper : Tree<Node<'T>>
    with
    static member Add (value : 'T) (tree : Tree<'T>) : Tree<'T> =
        match tree with
        | Empty -> Single value
        | Single a -> Deep (One value, Empty)
        | Deep (One a, deeper) -> Deep (Two (value, a), deeper)
        | Deep (Two (b, a), deeper) -> Deep (One value, deeper |> Tree.Add (Node2 (b, a)))

let rec add (value : 'T) (tree : Tree<'T>) : Tree<'T> =
    match tree with
    | Empty -> Single value
    | Single a -> Deep (One value, Empty)
    | Deep (One a, deeper) -> Deep (Two (value, a), deeper)
    | Deep (Two (b, a), deeper) -> Deep (One value, deeper |> add (Node2 (b, a)))

请注意，静态方法 Add 和函数 add 具有相同的实现，并且都以递归方式调用自身。

前者编译正常，后者报错：

Type mismatch. Expecting a
    Tree<Node<'T>> -> Tree<Node<'T>>    
but given a
    Tree<'T> -> Tree<'T>    
The resulting type would be infinite when unifying ''T' and 'Node<'T>'

Answer 1

在自由浮动函数add中，泛型类型参数属于函数本身(add<'T>)。

但是，在静态成员函数中，类型参数实际上属于class(Tree<'T>).

为什么这很重要？因为当你引用函数本身时，除非另有说明，否则编译器会假定类型参数不变。它不会猜测不同的错误，因为这可能会隐藏一大类类型不匹配错误。

但是，对于函数所属的类型，它并没有做出相同的假设。

如果您检查参数，对 add 的调用被假定为对 add<'T> 的调用，这会导致无限泛型递归并且无法编译。

但是，对Tree.Add的调用被推断为对Tree<Node<'T>>.Add的调用，不是对Tree<'T>.Add。这是完全不同的函数调用。

如果您显式注释类型：

static member Add (value : 'T) (tree : Tree<'T>) : Tree<'T> =
    // ...
    | Deep (Two (b, a), deeper) -> Deep (One value, deeper |> Tree<'T>.Add (Node2 (b, a)))

您将得到与自由函数完全相同的类型不匹配/无限类型错误。

同样，如果将其设为实例成员并引用同一实例，则会出现错误：

member this.Add (value : 'T) (tree : Tree<'T>) : Tree<'T> =
    // ...
    | Deep (Two (b, a), deeper) -> Deep (One value, deeper |> this.Add (Node2 (b, a)))

反之，你可以通过注解类型参数让自由函数编译，这样编译器就不会假设"it's the same symbol, so must refer to the same value":

let rec add<'T> (value : 'T) (tree : Tree<'T>) : Tree<'T> =
    // ...
    | Deep (Two (b, a), deeper) -> Deep (One value, deeper |> add (Node2 (b, a)))

F# 递归类型：方法与函数类型推断差异

F# recursive type: method vs function type inference differences

f#

type-inference

recursive-datastructures

recursive-type