Рекурсивный тип F#: различия в выводе типа метода и функции

Может кто-нибудь объяснить, почему в F# вывод типа работает по-разному (или какой-то другой аспект, который я не понимаю?) между методами класса и функциями.

Представьте себе следующее (упрощенно):

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>'

f# type-inference recursive-type recursive-datastructures
person Regent    schedule 20.05.2016    source источник

Ответы (1)


arrow_upward
3
arrow_downward

В свободно плавающей функции add параметр универсального типа принадлежит самой функции (add<'T>).

Однако в статической функции-члене параметр типа фактически принадлежит классу (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)))

И наоборот, вы можете компилировать бесплатную функцию, аннотируя параметр типа, чтобы компилятор не предполагал, что «это тот же символ, поэтому он должен ссылаться на одно и то же значение»:

let rec add<'T> (value : 'T) (tree : Tree<'T>) : Tree<'T> =
    // ...
    | Deep (Two (b, a), deeper) -> Deep (One value, deeper |> add (Node2 (b, a)))
person piaste    schedule 20.05.2016
comment
На самом деле помогло даже простое добавление аргумента типа в привязку функции 'let rec add‹'T›...'. - person Regent; 20.05.2016
comment
О, классно. Кажется, что компилятор делает предположение об одном и том же экземпляре только в том случае, если имя точно такое же. Я исправил свой ответ. - person piaste; 20.05.2016