フィンガーツリーを実装するときのタイプエラー

Question

Hinze（Haskell）の論文に記載されているように2-3本の指の木で遊んでみたかったです（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> 

私はちょうどviewl機能の作業を取得することができない今、それは型の不一致文句：2-3フィンガーツリー<を期待

「>が、> 2-3フィンガーツリーを与えられました。

'' 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で前にこのエラーが発生しましたが、機能上の完全な型情報を追加することによって、それを解決することができました。 viewlについては

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

これは十分ではないようですので、私はまた、（コメントを探してください）関数の途中でタイプを追加しようとしました。それはうまくいかなかった。

私はある種のエラーを理解しており、どこから来ているのですか。誰も私にどのようにこれを働かせるか教えてもらえますか？ IMHO、可能ならば、そうでなければprependもコンパイルされないだろうから。おそらくthisのようなトリックが役立ちますか？ （しかし、それを理解していない）。

---

PS：コードをFsSnipに貼り付けて、ブラウザで再生することもできます。

Answer 1

viewlまたはprependのような機能は、polymorphic recursionに依存します。prependへの再帰呼び出しでは、元の呼び出しとは異なる型の引数が使用されます。 F＃でそのような関数を定義することはできますが、発見したようにフル型の注釈が必要です（そうしないと、非常に混乱したエラーメッセージが表示されます）。特に、型パラメータは関数の定義で明示的でなければならないことに注意してください（通常は呼び出しサイトで推論できます）。最初の問題は、定義にviewl<'a>を指定する必要があることです。

しかし、非常に微妙な第2の問題があります。これはDigit<_>.OfListです。最初のチャンクをF＃インタラクティブに送信して、結果の定義のシグネチャを確認してみてください：static member OfList : (obj list -> Digit<obj>)が表示され、viewlを正しく定義できなくなります。どうしたの？ OfListに署名していないので、一般的な方法ではありません（機能は一般化されますが、メンバーは決してなりません）。しかし、コンパイラは入力リストの型が'a listであることを推測できません。'aはタイプの汎用パラメータです - int listまたはstring listなどではなく、この特定の型を推測するのはなぜですか？したがって、別の具体的な単相型に制約するために後続のコードで何かをしない限り、退屈な単形デフォルト（obj list）を選択します。代わりに、Digitに署名を追加する必要があり、すべて正常になります。

多くの場合、F＃では、ToListなどの関連する関数を定義するためにタイプごとに別々のモジュールを作成することは慣習的です。関数の定義は一般化されているため、ここで直面する問題も回避されます。つまり、あなたがこのようなあなたのコードを構造化することができます：

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