Ошибка типа при реализации пальчиковых деревьев

Question

Я хотел поиграть с 2-3 пальцами, как описано в статье (Haskell) Хинце (см. Также этот блог).

type Node<'a> =
    | Node2 of 'a * 'a
    | Node3 of 'a * 'a * 'a

    static member OfList = function
        | [a; b] -> Node2(a, b)
        | [a; b; c] -> Node3(a, b, c)
        | _ -> failwith "Only lists of length 2 or 3 accepted!"

    member me.ToList () =
        match me with
        | Node2(a, b) -> [a; b]
        | Node3(a, b, c) -> [a; b; c]

type Digit<'a> =
    | One of 'a
    | Two of 'a * 'a
    | Three of 'a * 'a * 'a
    | Four of 'a * 'a * 'a * 'a

    static member OfList = function
        | [a] -> One(a)
        | [a; b] -> Two(a, b)
        | [a; b; c] -> Three(a, b, c)
        | [a; b; c; d] -> Four(a, b, c, d)
        | _ -> failwith "Only lists of length 1 to 4 accepted!"

    member me.ToList () =
        match me with
        | One a -> [a]
        | Two(a, b) -> [a; b]
        | Three(a, b, c) -> [a; b; c]
        | Four(a, b, c, d) -> [a; b; c; d]

    member me.Append x =
        match me with
        | One a -> Two(a, x)
        | Two(a, b) -> Three(a, b, x)
        | Three(a, b, c) -> Four(a, b, c, x)
        | _ -> failwith "Cannot prepend to Digit.Four!"

    member me.Prepend x =
        match me with
        | One a -> Two(x, a)
        | Two(a, b) -> Three(x, a, b)
        | Three(a, b, c) -> Four(x, a, b, c)
        | _ -> failwith "Cannot prepend to Digit.Four!"

[<NoComparison>]
[<NoEquality>]
type FingerTree<'a> =
    | Empty
    | Single of 'a
    | Deep of Digit<'a> * FingerTree<Node<'a>> * Digit<'a>

type Digit<'a> with
    member me.Promote () =
        match me with
        | One a -> Single a
        | Two(a, b) -> Deep(One a, Empty, One b)
        | Three(a, b, c) -> Deep(One a, Empty, Two(b, c))
        | Four(a, b, c, d) -> Deep(Two(a, b), Empty, Two(c, d))

type View<'a> = Nil | View of 'a * FingerTree<'a>

Теперь я просто не могу получить viewl Функция работает, жалуется на несоответствие типов:

Ожидается FingerTree <'a>, но задано FingerTree>.

Результирующий тип будет бесконечным при объединении ''a'и' Node <'a>' FingerTree.

let rec viewl : FingerTree<'a> -> View<'a> = function
    | Empty -> Nil
    | Single x -> View(x, Empty)
    | Deep(One x, deeper(*:FingerTree<'a>/FingerTree<Node<'a>>*), suffix) ->
        let rest =
            match viewl deeper with
            | Nil ->
                suffix.Promote()
            | View (node(*:Node<'a>*), rest) ->
                let prefix = node.ToList() |> Digit<_>.OfList
                Deep(prefix, rest, suffix)
        View(x, rest)
    | Deep(prefix, deeper, suffix) ->
        match prefix.ToList() with
        | x::xs ->
            View(x, Deep(Digit<_>.OfList xs, deeper, suffix))
        | _ -> failwith "Impossible!"

У меня была эта ошибка раньше prepend но смог решить ее, добавив полную информацию о типе функции.

// These three/four type annotations solved the problem.
let rec prepend<'a> (a:'a) : FingerTree<'a> -> FingerTree<'a> = function
    | Empty -> Single a
    | Single b -> Deep(One a, Empty, One b)
    | Deep(Four(b, c, d, e), deeper, suffix) ->
        Deep(Two(a, b), prepend (Node3(c, d, e)) deeper, suffix)
    | Deep(prefix, deeper, suffix) ->
        Deep(prefix.Prepend a, deeper, suffix)

За viewl кажется, этого недостаточно, поэтому я также попытался добавить типы в середине функции (ищите комментарии). Это не сработало.

Я вроде понимаю ошибку и откуда она исходит. Может кто-нибудь сказать мне, как заставить это работать? ИМХО, это должно быть возможно, потому что иначе prepend также не будет компилироваться. Может быть, помогает такой трюк? (Не понимаю, хотя).

---

PS: я также поместил код в FsSnip для игры в браузере.

Answer 1

Функции как viewl или же prepend полагаться на полиморфную рекурсию: рекурсивный вызов prepend принимает аргумент другого типа, чем исходный вызов. Вы можете определить такие функции в F#, но, как вы обнаружили, они требуют аннотаций полного типа (иначе вы получите очень запутанное сообщение об ошибке). В частности, обратите внимание, что параметры типа должны быть явными в определении функции (хотя они обычно могут быть выведены на сайтах вызовов). Итак, первая проблема заключается в том, что вам нужно указать viewl<'a> в определении.

Тем не менее, есть очень тонкая вторая проблема, которая касается Digit<_>.OfList, Попробуйте отправить первый фрагмент кода в F# интерактивно и посмотрите на подписи полученных определений: вы увидите static member OfList : (obj list -> Digit<obj>)что впоследствии сделает так, что viewl не может быть определен правильно. Так что же случилось? Вы не дали подпись OfList, так что это не будет универсальный метод (функции будут обобщены, но члены никогда не будут). Но компилятор также не может сделать вывод, что вы хотели, чтобы входной список имел тип 'a list где 'a является универсальным параметром типа - почему он выводит этот конкретный тип, а не int list или же string list, так далее.? Таким образом, он выбирает скучный мономорфный по умолчанию (obj list), если вы не сделаете что-то в последующем коде, чтобы ограничить его другим конкретным мономорфным типом. Вместо этого вам нужно добавить подпись Digit и тогда все будет хорошо.

Часто в F# идиоматично создавать отдельный модуль для каждого типа для определения связанных функций, таких как ToListи т. д. Поскольку определения функций обобщены, это также позволило бы избежать Digit проблема, с которой вы сталкиваетесь здесь. То есть вы можете структурировать свой код следующим образом:

type Node<'a> =
    | Node2 of 'a * 'a
    | Node3 of 'a * 'a * 'a

module Node =
    let ofList = function
    | [a; b] -> Node2(a, b)
    | [a; b; c] -> Node3(a, b, c)
    | _ -> failwith "Only lists of length 2 or 3 accepted!"

    let toList = function
    | Node2(a, b) -> [a; b]
    | Node3(a, b, c) -> [a; b; c]

type Digit<'a> =
    | One of 'a
    | Two of 'a * 'a
    | Three of 'a * 'a * 'a
    | Four of 'a * 'a * 'a * 'a

[<NoComparison>]
[<NoEquality>]
type FingerTree<'a> =
    | Empty
    | Single of 'a
    | Deep of Digit<'a> * FingerTree<Node<'a>> * Digit<'a>

module Digit =
    let ofList = function
    | [a] -> One(a)
    | [a; b] -> Two(a, b)
    | [a; b; c] -> Three(a, b, c)
    | [a; b; c; d] -> Four(a, b, c, d)
    | _ -> failwith "Only lists of length 1 to 4 accepted!"

    let toList = function
    | One a -> [a]
    | Two(a, b) -> [a; b]
    | Three(a, b, c) -> [a; b; c]
    | Four(a, b, c, d) -> [a; b; c; d]

    let append x = function
    | One a -> Two(a, x)
    | Two(a, b) -> Three(a, b, x)
    | Three(a, b, c) -> Four(a, b, c, x)
    | _ -> failwith "Cannot prepend to Digit.Four!"

    let prepend x = function
    | One a -> Two(x, a)
    | Two(a, b) -> Three(x, a, b)
    | Three(a, b, c) -> Four(x, a, b, c)
    | _ -> failwith "Cannot prepend to Digit.Four!"

    let promote = function
    | One a -> Single a
    | Two(a, b) -> Deep(One a, Empty, One b)
    | Three(a, b, c) -> Deep(One a, Empty, Two(b, c))
    | Four(a, b, c, d) -> Deep(Two(a, b), Empty, Two(c, d))

type View<'a> = Nil | View of 'a * FingerTree<'a>

let rec viewl<'a> : FingerTree<'a> -> View<'a> = function
    | Empty -> Nil
    | Single x -> View(x, Empty)
    | Deep(One x, deeper, suffix) ->
        let rest =
            match viewl deeper with
            | Nil -> suffix |> Digit.promote
            | View (node, rest) ->
                let prefix = node |> Node.toList |> Digit.ofList
                Deep(prefix, rest, suffix)
        View(x, rest)
    | Deep(prefix, deeper, suffix) ->
        match prefix |> Digit.toList with
        | x::xs ->
            View(x, Deep(Digit.ofList xs, deeper, suffix))
        | _ -> failwith "Impossible!"