हास्केल में पंक्ति बहुलकता: "ट्रांसफॉर्मेशन"

Question

के साथ फर्थ डीएसएल लिखने में परेशानी मुझे हाल ही में हास्केल ब्लॉग गतिविधि से प्रेरित किया गया है ताकि हास्केल में एक फर्थ-जैसी डीएसएल लिखने पर मेरा हाथ आ सकें। दृष्टिकोण मैं ले लिया है एक साथ सीधा और भ्रामक है:

{-# LANGUAGE TypeOperators, RankNTypes, ImpredicativeTypes #-} 

-- a :~> b represents a "stack transformation" 
--   from stack type "a" to stack type "b" 
-- a :> b represents a "stack" where the top element is of type "b" 
--   and the "rest" of the stack has type "a" 
type s :~> s' = forall r. s -> (s' -> r) -> r 
data a :> b = a :> b deriving Show 
infixl 4 :> 

सरल काम करने के लिए, यह काफी अच्छी तरह से काम करता है:

start :: (() -> r) -> r 
start f = f() 

end :: (() :> a) -> a 
end (() :> a) = a 

stack x f = f x 
runF s = s end 
_1 = liftS0 1 
neg = liftS1 negate 
add = liftS2 (+) 

-- aka "push" 
liftS0 :: a -> (s :~> (s :> a)) 
liftS0 a s = stack $ s :> a 

liftS1 :: (a -> b) -> ((s :> a) :~> (s :> b)) 
liftS1 f (s :> a) = stack $ s :> f a 

liftS2 :: (a -> b -> c) -> ((s :> a :> b) :~> (s :> c)) 
liftS2 f (s :> a :> b) = stack $ s :> f a b 

सरल कार्यों तुच्छता से उनकी संगत ढेर परिवर्तनों में तब्दील किया जा सकता है। कुछ खेल के चारों ओर सुखद परिणाम प्राप्त होते हैं अब तक:

ghci> runF $ start _1 _1 neg add 
0 

मुसीबत आता है जब मैं उच्च क्रम कार्यों के साथ इस विस्तार करने के लिए प्रयास करें।

-- this requires ImpredicativeTypes...not really sure what that means 
-- also this implementation seems way too simple to be correct 
-- though it does typecheck. I arrived at this after pouring over types 
-- and finally eta-reducing the (s' -> r) function argument out of the equation 
-- call (a :> f) h = f a h 
call :: (s :> (s :~> s')) :~> s' 
call (a :> f) = f a 

call, प्रपत्र s के रूप (s :> (s :~> s')) के ढेर को बदलने के लिए अनिवार्य रूप से द्वारा इसके बारे में "आराम" करने के लिए "लागू करने के" परिवर्तन (ढेर की नोक पर आयोजित) माना जाता है। मुझे लगता है यह चाहिए काम इस तरह:

ghci> runF $ start _1 (liftS0 neg) call 
-1 

लेकिन वास्तविकता में, यह मेरे एक विशाल प्रकार मेल नहीं खाता त्रुटि देता है। मैं क्या गलत कर रहा हूं? क्या "ढेर परिवर्तन" प्रतिनिधित्व पर्याप्त रूप से उच्च-आदेश कार्यों को संभाल सकता है, या क्या मुझे इसे समायोजित करने की आवश्यकता है?

एनबी। start push 1 push 2 add end के बजाय, इन लोगों ने इसे कैसे किया, इसके विपरीत, मैं इसे runF $ start (push 1) (push 2) add होना चाहता हूं, यह विचार यह है कि शायद बाद में मैं कुछ टाइपक्लास जादू का काम कर सकता हूं ताकि push कुछ अक्षरों के लिए अंतर्निहित हो सके।

• https://github.com/leonidas/codeblog/blob/master/2012/2012-02-17-concatenative-haskell.md
• https://gist.github.com/1847747

Answer 1

आपका :~> प्रकार वह नहीं है जो आप वास्तव में चाहते हैं (इसलिए ImpredicativeTypes)। यदि आप call से टाइप एनोटेशन हटाते हैं तो आपका अंतिम नमूना अपेक्षित के रूप में काम करेगा। यह काम करने के लिए एक और तरीका है अतिरिक्त पैरामीटर के साथ कम फैंसी लेकिन अधिक उपयुक्त प्रकार का उपयोग करने के लिए है:

type Tran s s' r = s -> (s' -> r) -> r 

call :: Tran (s :> (Tran s s' r)) s' r 
call (a :> f) = f a 

लेकिन क्या आप के बाद कर रहे हैं एक अच्छा डीएसएल वाक्य रचना है और आप बर्दाश्त कर सकते हैं OverlappingInstances तो आप भी काफी प्राप्त कर सकते हैं कर रहे हैं liftSx कार्यों से छुटकारा:

{-# LANGUAGE TypeOperators, MultiParamTypeClasses, TypeFamilies, 
      FlexibleInstances, FlexibleContexts, 
      UndecidableInstances, IncoherentInstances #-} 

data a :> b = a :> b deriving Show 
infixl 4 :> 


class Stackable s o r where 
    eval :: s -> o -> r 


data End = End 

instance (r1 ~ s) => Stackable s End r1 where 
    eval s End = s 


instance (Stackable (s :> a) o r0, r ~ (o -> r0)) => Stackable s a r where 
    eval s a = eval (s :> a) 

instance (a ~ b, Stackable s c r0, r ~ r0) => Stackable (s :> a) (b -> c) r where 
    eval (s :> a) f = eval s (f a) 

-- Wrap in Box a function which should be just placed on stack without immediate application 
data Box a = Box a 

instance (Stackable (s :> a) o r0, r ~ (o -> r0)) => Stackable s (Box a) r where 
    eval s (Box a) = eval (s :> a) 


runS :: (Stackable() a r) => a -> r 
runS a = eval() a 

-- tests 
t1 = runS 1 negate End 
t2 = runS 2 1 negate (+) End 

t3 = runS 1 (Box negate) ($) End 
t4 = runS [1..5] 0 (Box (+)) foldr End 
t5 = runS not True (flip ($)) End 

t6 = runS 1 (+) 2 (flip ($)) End 

Answer 2

समस्या यह है कि अपने प्रकार पर्याय एक बहुरूपी प्रकार

type s :~> s' = forall r. s -> (s' -> r) -> r 

एक प्रकार से -> है अन्य निर्माता के लिए एक तर्क के रूप बहुरूपी प्रकार का उपयोग करना है "अपर्याप्तता" कहा जाता है। उदाहरण के लिए, निम्नलिखित एक impredicative उपयोग

Maybe (forall a. a -> a) 

विभिन्न कारणों से हो सकता है, impredicativity साथ प्रकार निष्कर्ष, कठिन है यही कारण है कि GHC शिकायत है। (नाम "impredicative" तर्क और करी-Howards समाकृतिकता से आता है।)

आपके मामले में, समाधान एक निर्माता के साथ एक बीजीय डेटा प्रकार का उपयोग करने के लिए बस है: मूल रूप से

data s :~> s' = StackArr { runStackArr :: forall r. s -> (s' -> r) -> r} 

, स्पष्ट कन्स्ट्रक्टर StackArr प्रकार चेकर के लिए पर्याप्त संकेत प्रदान करता है।

वैकल्पिक रूप से, आप ImpredicativeTypes भाषा एक्सटेंशन का प्रयास कर सकते हैं।