Typ Fehler bei der Implementierung Finger Bäume

Question

Ich wollte mit 2-3 Finger Bäume herumspielen, wie in der (Haskell) Papier von Hinze beschrieben (siehe auch diese blog).

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> 

Jetzt kann ich die viewl Funktion Arbeits einfach nicht, klagt es über eine Typenkonflikt:

eine FingerTree < ‚eine Schwangerschaft> aber eine FingerTree gegeben>.

Der resultierende Typ wäre unendlich, wenn "a" und "Node < 'a' 'FingerTree vereinheitlicht würden.

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!" 

hatte ich diesen Fehler vor in prepend aber konnte es lösen, indem sie die volle Art Informationen über die Funktion hinzufügen.

// 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) 

Für viewl dies scheint nicht genug zu sein, also habe ich versucht, auch Typen in der Mitte der Funktion (achten Sie auf die Kommentare) hinzufügen. Es hat nicht funktioniert.

Ich verstehe den Fehler und woher es kommt. Kann mir jemand sagen, wie man das funktioniert? IMHO sollte es möglich sein, denn sonst würde prepend auch nicht kompilieren. Vielleicht hilft ein Trick wie this? (Versteh es aber nicht).

---

PS: Ich habe auch den Code auf FsSnip für das Spiel um im Browser.

Answer 1

Funktionen wie viewl oder prepend verlassen sich auf polymorphic recursion: der rekursive Aufruf prepend ein Argument von einem anderen Typ als der ursprüngliche Anruf. Sie können solche Funktionen in F # definieren, aber wie Sie festgestellt haben, benötigen sie volle Typ Anmerkungen (oder Sie erhalten eine sehr verwirrende Fehlermeldung). Beachten Sie insbesondere, dass die Typparameter in der Definition der Funktion explizit sein müssen (obwohl sie typischerweise an Aufrufstellen abgeleitet werden können). Das erste Problem besteht darin, dass Sie in der Definition viewl<'a> angeben müssen.

Allerdings gibt es ein äußerst subtiles zweites Problem, das betrifft Digit<_>.OfList. Versuchen Sie, den ersten Codeabschnitt an F # interactive zu senden, und sehen Sie sich die Signaturen der resultierenden Definitionen an: Sie werden static member OfList : (obj list -> Digit<obj>) sehen, was dazu führt, dass viewl nicht korrekt definiert werden kann. Also was ist passiert? Sie haben keine Signatur an OfList vergeben, also wird es keine generische Methode sein (Funktionen werden verallgemeinert, aber Mitglieder werden nie sein). Aber der Compiler kann auch nicht ableiten, dass Sie für die Eingabeliste den Typ 'a list haben wollten, wobei 'a der generische Parameter des Typs ist - warum würde er auf diesen spezifischen Typ und nicht auf int list oder string list usw. schließen? Daher wählt es einen langweiligen monomorphen Standard (obj list), es sei denn, Sie machen etwas im nachfolgenden Code, um es auf einen anderen konkreten monomorphen Typ zu beschränken. Stattdessen müssen Sie eine Signatur zu Digit hinzufügen und dann wird alles in Ordnung sein. In F # ist es oft idiomatisch, ein eigenes Modul pro Typ zu erstellen, um verwandte Funktionen wie ToList usw. zu definieren. Da Funktionsdefinitionen verallgemeinert sind, hätte dies auch das Digit Problem vermieden, dem Sie hier gegenüberstehen.Das heißt, Sie Ihren Code wie diese Struktur könnte:

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!"