Erreur de type lors de la mise en œuvre des arbres de doigt

Question

Je voulais jouer avec 2-3 arbres de doigt comme décrit dans le document (Haskell) par Hinze (voir aussi ce 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> 

Maintenant, je ne peux pas obtenir le fonctionnement de la fonction viewl, il se plaint d'une incompatibilité de type:

Attendre un fingertree < « a> mais donné une fingertree>.

Le type résultant serait infini lors de l'unification de '' a 'et' 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!" 

J'ai eu cette erreur avant de prepend, mais a été en mesure de le résoudre en ajoutant toute information de type sur la fonction.

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

Pour viewl cela ne semble pas être assez, alors j'ai essayé aussi d'ajouter des types au milieu de la fonction (chercher les commentaires). Ça n'a pas marché. Je comprends en quelque sorte l'erreur et d'où elle vient. Quelqu'un peut-il me dire comment faire fonctionner cela? À mon humble avis, il devrait être possible, car sinon prepend ne compilerait pas non plus. Peut-être un truc comme this aide? (Ne le comprends pas).

---

PS: Je mets également le code sur FsSnip pour jouer autour dans le navigateur.

Answer 1

Les fonctions comme viewl ou prepend s'appuient sur polymorphic recursion: l'appel récursif à prepend prend un argument d'un type différent de l'appel d'origine. Vous pouvez définir de telles fonctions dans F #, mais comme vous l'avez découvert, elles nécessitent des annotations de type full (sinon vous obtenez un message d'erreur très confus). En particulier, notez que les paramètres de type doivent être explicites dans la définition de la fonction (bien qu'ils puissent généralement être déduits sur les sites d'appel). Donc, le premier problème est que vous devez spécifier viewl<'a> dans la définition.

Cependant, il existe un deuxième problème extrêmement subtil, qui concerne Digit<_>.OfList. Essayez d'envoyer le premier bloc de code à F # interactif et en regardant les signatures des définitions résultantes: vous verrez static member OfList : (obj list -> Digit<obj>), ce qui fera en sorte que viewl ne peut pas être défini correctement. Alors, qu'est-ce-qu'il s'est passé? Vous n'avez pas donné de signature à OfList, donc ce ne sera pas une méthode générique (les fonctions seront généralisées, mais les membres ne le seront jamais). Mais le compilateur ne peut pas non plus déduire que vous vouliez que la liste d'entrée soit de type 'a list où le 'a est le paramètre générique du type - pourquoi en déduire ce type spécifique plutôt que int list ou string list, etc.? Il choisit donc un défaut monomorique ennuyeux (obj list), sauf si vous faites quelque chose dans le code suivant pour le contraindre à un type monomorphe concret différent. Au lieu de cela, vous devez ajouter une signature à Digit et tout ira bien.

Souvent en F #, il est idiomatiques de créer un module séparé par type pour définir les fonctions connexes comme ToList, etc. Puisque les définitions de fonctions sont généralisées, cela aurait également évité le problème Digit vous faites face ici.Autrement dit, vous pouvez structurer votre code comme ceci:

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