प्रकार त्रुटि जब उंगली पेड़

Question

मैं Hinze द्वारा (हास्केल) पत्र में वर्णित के रूप में 2-3 उंगली के पेड़ के साथ चारों ओर खेलना चाहते थे लागू करने (यह भी देखें इस blog)। >

उम्मीद एक FingerTree < 'एक> लेकिन एक FingerTree दिया:

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 एकीकृत

जिसके परिणामस्वरूप प्रकार अनंत होगा।

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 भी संकलित नहीं होगा। शायद this की तरह एक चाल मदद करता है? (हालांकि इसे समझ में नहीं आता)।

---

पुनश्च: मैं भी कोड FsSnip पर ब्राउज़र में चारों ओर खेलने के लिए डाल दिया।

Answer 1

कार्य viewl या prepend तरह polymorphic recursion पर भरोसा करते हैं: prepend को पुनरावर्ती कॉल मूल कॉल की तुलना में एक अलग तरह के एक तर्क लेता है। आप F # में ऐसे फ़ंक्शंस को परिभाषित कर सकते हैं, लेकिन जैसा कि आपने पाया है उन्हें पूर्ण टाइप एनोटेशन (या फिर आपको एक बहुत भ्रमित त्रुटि संदेश मिलता है) की आवश्यकता होती है। विशेष रूप से, ध्यान दें कि प्रकार पैरामीटर फ़ंक्शन की परिभाषा में स्पष्ट होना चाहिए (हालांकि उन्हें आम तौर पर कॉल साइटों पर अनुमानित किया जा सकता है)। तो पहली समस्या यह है कि आपको परिभाषा में viewl<'a> निर्दिष्ट करने की आवश्यकता है।

हालांकि, वहाँ एक बहुत ही सूक्ष्म दूसरी समस्या है, जो Digit<_>.OfList चिंताओं है। एफ # इंटरैक्टिव और जिसके परिणामस्वरूप परिभाषाओं के हस्ताक्षर को देखकर करने के लिए कोड के पहले हिस्सा भेजने का प्रयास करें: यदि आप static member OfList : (obj list -> Digit<obj>), जो बाद में यह कर देगा ताकि viewl सही ढंग से परिभाषित नहीं किया जा सकता देखेंगे। तो क्या हुआ? आपने OfList पर हस्ताक्षर नहीं दिया है, इसलिए यह एक सामान्य विधि नहीं होगी (कार्यों को सामान्यीकृत किया जाएगा, लेकिन सदस्य कभी नहीं होंगे)। लेकिन संकलक भी अनुमान नहीं लगा सकता है कि आप प्रकार 'a list जहां 'a प्रकार के सामान्य पैरामीटर है की होने के लिए इनपुट सूची के लिए लक्षित - क्यों यह नहीं बल्कि int list या string list, आदि की तुलना में इस विशेष प्रकार का अनुमान लगा होगा? इसलिए यह एक उबाऊ मोनोमोर्फिक डिफ़ॉल्ट (obj list) चुनता है, जब तक कि आप इसे बाद के कोड में कुछ अलग कंक्रीट मोनोमोर्फिक प्रकार तक सीमित न करें। इसके बजाय, आपको Digit पर एक हस्ताक्षर जोड़ने की आवश्यकता है और फिर सब ठीक हो जाएगा।

अक्सर एफ # में 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!"