जीएचसी: प्रेत प्रकार पैरामीटर का अनुमान लगाने में विफलता

Question

तो मैं चर-लंबाई लंबाई टुपल्स के लिए एक प्रकार बनाने की कोशिश कर रहा हूं, मूल रूप से Either a (Either (a,b) (Either (a,b,c) ...)) और Either (Either (Either ... (x,y,z)) (y,z)) z के एक सुंदर संस्करण के रूप में।

{-# LANGUAGE TypeOperators, TypeFamilies, MultiParamTypeClasses, FlexibleInstances #-} 
module Temp where 

-- type level addition 
data Unit 
data Succ n 

class Summable n m where 
    type Sum n m :: * 

instance Summable Unit m where 
    type Sum Unit m = Succ m 

instance Summable n m => Summable (Succ n) m where 
    type Sum (Succ n) m = Succ (Sum n m) 

-- variable length tuple, left-to-right 
data a :+ b = a :+ Maybe b 
infixr 5 :+ 

class Prependable t r s where 
    type Prepend t r s :: * 
    prepend :: r -> Maybe s -> Prepend t r s 

instance Prependable Unit x y where 
    type Prepend Unit x y = x :+ y 
    prepend = (:+) 

instance Prependable n x y => Prependable (Succ n) (w :+ x) y where 
    type Prepend (Succ n) (w :+ x) y = w :+ Prepend n x y 
    prepend (w :+ Nothing) _ = w :+ Nothing 
    prepend (w :+ Just x) y = w :+ Just (prepend x y) 

-- variable length tuple, right-to-left 
data a :- b = Maybe a :- b 
infixl 5 :- 

class Appendable t r s where 
    type Append t r s :: * 
    append :: Maybe r -> s -> Append t r s 

instance Appendable Unit x y where 
    type Append Unit x y = x :- y 
    append = (:-) 

instance Appendable n x y => Appendable (Succ n) x (y :- z) where 
    type Append (Succ n) x (y :- z) = Append n x y :- z 
    append _ (Nothing :- z) = Nothing :- z 
    append x (Just y :- z) = Just (append x y) :- z 

हालांकि, संकलक पुनरावर्ती मामलों में prepend या append का प्रेत प्रकार पैरामीटर का अनुमान लगा पाने में असमर्थ लगता है:

Temp.hs:32:40: 
    Could not deduce (Prepend t1 x y ~ Prepend n x y) 
    from the context (Prependable n x y) 
     bound by the instance declaration at Temp.hs:29:10-61 
    NB: `Prepend' is a type function, and may not be injective 
    In the return type of a call of `prepend' 
    In the first argument of `Just', namely `(prepend x y)' 
    In the second argument of `(:+)', namely `Just (prepend x y)' 

Temp.hs:49:34: 
    Could not deduce (Append t0 x y ~ Append n x y) 
    from the context (Appendable n x y) 
     bound by the instance declaration at Temp.hs:46:10-59 
    NB: `Append' is a type function, and may not be injective 
    In the return type of a call of `append' 
    In the first argument of `Just', namely `(append x y)' 
    In the first argument of `(:-)', namely `Just (append x y)' 

वहाँ है कुछ भी मैं संकलक मदद करने के लिए क्या कर सकते हैं इस निष्कर्ष बनाते हैं?

NB: `Prepend' is a type function, and may not be injective 

इसका क्या मतलब है:

Answer 1

त्रुटि संदेश यहाँ की महत्वपूर्ण हिस्सा है? इसका मतलब है कि कई instance Prependable हो सकते हैं जैसे कि उनके type Prepend ... = a, ताकि यदि आप a होने के लिए अनुमान लगाते हैं, तो आपको यह नहीं पता कि यह किस उदाहरण से संबंधित है।

आप data types in type families, लाभ यह है कि आप प्रकार काम करता है, जो surjective हैं, लेकिन injective हो सकता है, और बदले प्रकार "संबंधों" है, जो द्विभाजित हैं के साथ के साथ सौदा नहीं है जो का उपयोग करके इस हल कर सकते हैं (इसलिए हर Prepend प्रकार केवल एक प्रकार के परिवार से संबंधित हो सकता है, और प्रत्येक प्रकार के परिवार के पास एक अलग Prepend प्रकार है)।

(तुम मुझे एक टिप्पणी प्रकार परिवारों में डेटा प्रकार के साथ एक समाधान दिखा छोड़ने के लिए चाहते हैं! असल में, बस का उपयोग एक data Prependtype Prepend के बजाय)

Answer 2

समाधान मैं के साथ आया एक डमी तर्क जोड़ने के लिए था prepend और append टाई प्रेत पैरामीटर के लिए:

-- as above, except... 

unsucc :: Succ n -> n 
unsucc _ = undefined 

class Prependable t r s where 
    type Prepend t r s :: * 
    prepend :: t -> r -> Maybe s -> Prepend t r s 

instance Prependable Unit x y where 
    type Prepend Unit x y = x :+ y 
    prepend _ = (:+) 

instance Prependable n x y => Prependable (Succ n) (w :+ x) y where 
    type Prepend (Succ n) (w :+ x) y = w :+ Prepend n x y 
    prepend _ (w :+ Nothing) _ = w :+ Nothing 
    prepend t (w :+ Just x) y = w :+ Just (prepend (unsucc t) x y) 

class Appendable t r s where 
    type Append t r s :: * 
    append :: t -> Maybe r -> s -> Append t r s 

instance Appendable Unit x y where 
    type Append Unit x y = x :- y 
    append _ = (:-) 

instance Appendable n x y => Appendable (Succ n) x (y :- z) where 
    type Append (Succ n) x (y :- z) = Append n x y :- z 
    append _ _ (Nothing :- z) = Nothing :- z 
    append t x (Just y :- z) = Just (append (unsucc t) x y) :- z