मैं हास्केल में लिस्प के आवेदन को कैसे परिभाषित करूं?

Question

क्या इस परिभाषा को आलसी भाषा जैसी आलसी भाषा में अनुमति नहीं दी जानी चाहिए जिसमें कार्यवाही की जाती है?

apply f [] = f 
apply f (x:xs) = apply (f x) xs 

यह मूल रूप से तर्क की दी गई सूची को दिया समारोह लागू होता है और बहुत आसानी से उदाहरण के लिए लिस्प में किया जाता है कि एक समारोह है। क्या कोई कामकाज है?

Answer 1

यह apply कार्य करने के लिए एक स्थिर प्रकार देना कठिन है, क्योंकि उसके प्रकार (संभवतः विषम) सूची तर्क के प्रकार पर निर्भर करता है। कर रहे हैं कम से कम हास्केल में इस समारोह है कि मैं के बारे में सोच सकते हैं लिखने के लिए दो एक तरीके:

प्रतिबिंब का उपयोग करना

हम क्रम तक आवेदन के प्रकार की जाँच को स्थगित कर सकते हैं:

import Data.Dynamic 
import Data.Typeable 

apply :: Dynamic -> [Dynamic] -> Dynamic 
apply f []  = f 
apply f (x:xs) = apply (f `dynApp` x) xs 

ध्यान दें कि अब हास्केल प्रोग्राम रनटाइम पर एक प्रकार त्रुटि के साथ विफल हो सकता है।

वाया प्रकार वर्ग प्रत्यावर्तन

अर्द्ध मानक Text.Printf चाल (augustss, IIRC द्वारा आविष्कार) का उपयोग करना, एक समाधान in this style (व्यायाम) ऊपर कोडित किया जा सकता है। हालांकि यह बहुत उपयोगी नहीं हो सकता है, और अभी भी सूची में प्रकारों को छिपाने के लिए कुछ चाल की आवश्यकता है।

संपादित करें: मैं गतिशील प्रकार या hlists/अस्तित्वों का उपयोग किए बिना इसे लिखने के तरीके से नहीं आ सकता था।

type 'a RecFunction = RecFunction of ('a -> 'a RecFunction) 
let rec apply (f: 'a RecFunction) (lst: 'a list) = 
    match (lst,f) with 
    | ([],_) -> f 
    | ((x::xs), RecFunction z) -> apply (z x) xs 

इस मामले में: एक उदाहरण

Answer 2

यह कोड स्थिर और गतिशील प्रकार-जांच के बीच अंतरों का एक अच्छा उदाहरण है। स्थिर प्रकार की जांच के साथ, संकलक यह सुनिश्चित नहीं कर सकता कि apply f वास्तव में उन तर्कों को पारित किया जा रहा है जो f अपेक्षा करते हैं, इसलिए यह प्रोग्राम को अस्वीकार कर देता है। लिस्प में, रनटाइम पर जांच की जाती है और प्रोग्राम तब विफल हो सकता है।

Answer 3

नहीं, यह नहीं हो सकता है। f और f x विभिन्न प्रकार हैं। हैकेल की स्थाई रूप से टाइप की गई प्रकृति के कारण, यह कोई फ़ंक्शन नहीं ले सकता है। इसे एक विशिष्ट प्रकार का कार्य करना है।

मान लीजिए fa -> b -> c प्रकार के साथ पास किया गया है। फिर f x में b -> c टाइप किया गया है। लेकिन a -> b -> c में a -> b जैसा ही होना चाहिए। इसलिए a -> (b -> c) प्रकार का एक कार्य a -> b प्रकार का कार्य होना चाहिए। तो bb -> c जैसा होना चाहिए, जो एक अनंत प्रकार b -> b -> b -> ... -> c है। यह अस्तित्व में नहीं हो सकता है। (b के लिए b -> c स्थानापन्न करने के लिए जारी)

Answer 4

देखने के लिए मुझे यकीन है कि यह कितना मददगार होगा के रूप में मैं एफ # में यह लिख रहा हूँ नहीं हूँ, लेकिन मैं यह आसानी से भी हास्केल में किया जा सकता है लगता है प्यार करोगे सवाल में "एफ" एक भेदभाव संघ का उपयोग करके परिभाषित किया गया है जो पुनरावर्ती डेटा प्रकार परिभाषा की अनुमति देता है। इसका अनुमान लगाया गया समस्या हल करने के लिए इसका उपयोग किया जा सकता है।

Answer 5

जीएचसी में ऐसा करने का एक तरीका यहां है। जीएचसी को मनाने के लिए आपको यहां और वहां कुछ प्रकार की टिप्पणियों की आवश्यकता होगी कि यह सब काम करने जा रहा है।

{-# LANGUAGE MultiParamTypeClasses #-} 
{-# LANGUAGE FunctionalDependencies #-} 
{-# LANGUAGE FlexibleInstances #-} 
{-# LANGUAGE UndecidableInstances #-} 
{-# LANGUAGE IncoherentInstances #-} 

class Apply f a r | f -> a r where 
    apply :: f -> [a] -> r 
instance Apply f a r => Apply (a -> f) a r where 
    apply f (a:as) = apply (f a) as 
instance Apply r a r where 
    apply r _ = r 

test = apply ((+) :: Int -> Int -> Int) [1::Int,2] 

apply' :: (a -> a -> a) -> [a] -> a 
apply' = apply 

test' = apply' (+) [1,2] 

Answer 6

मैं जोएर्ड Visscher के जवाब पसंद है, लेकिन एक्सटेंशन - विशेष रूप से IncoherentInstances, इस मामले में इस्तेमाल किया आंशिक आवेदन संभव बनाने के लिए - थोड़ा कठिन हो सकता है। यहां एक समाधान है जिसके लिए किसी भी एक्सटेंशन की आवश्यकता नहीं है।

सबसे पहले, हम कार्यों के डेटाटाइप को परिभाषित करते हैं जो जानते हैं कि किसी भी तर्क के साथ क्या करना है। आपको "रिटर्न टाइप" होने के रूप में "तर्क प्रकार" और b होने के रूप में a पढ़ना चाहिए।

data ListF a b = Cons b (ListF a (a -> b)) 

फिर हम कुछ (हास्केल) कार्यों को लिख सकते हैं जो इन (विविधता) कार्यों को व्यवस्थित करते हैं। मैं प्रीलूड में होने वाले किसी भी फ़ंक्शन के लिए F प्रत्यय का उपयोग करता हूं।

headF :: ListF a b -> b 
headF (Cons b _) = b 

mapF :: (b -> c) -> ListF a b -> ListF a c 
mapF f (Cons v fs) = Cons (f v) (mapF (f.) fs) 

partialApply :: ListF a b -> [a] -> ListF a b 
partialApply fs   []  = fs 
partialApply (Cons f fs) (x:xs) = partialApply (mapF ($x) fs) xs 

apply :: ListF a b -> [a] -> b 
apply f xs = headF (partialApply f xs) 

उदाहरण के लिए, sum समारोह एक variadic समारोह के रूप में के बारे में सोचा जा सकता है:

sumF :: Num a => ListF a a 
sumF = Cons 0 (mapF (+) sumF) 

sumExample = apply sumF [3, 4, 5] 

हालांकि, हम भी सामान्य कार्यों, जो जरूरी नहीं जानते से निपटने के लिए सक्षम होना चाहते हैं क्या किसी भी तर्क के साथ करने के लिए। इसलिए क्या करना है? खैर, लिस्प की तरह, हम रनटाइम पर अपवाद फेंक सकते हैं। नीचे, हम f का उपयोग गैर-वैरिएडिक फ़ंक्शन के एक साधारण उदाहरण के रूप में करेंगे।

f True True True = 32 
f True True False = 67 
f _ _ _ = 9 

tooMany = error "too many arguments" 
tooFew = error "too few arguments" 
lift0 v = Cons v tooMany 
lift1 f = Cons tooFew (lift0 f) 
lift2 f = Cons tooFew (lift1 f) 
lift3 f = Cons tooFew (lift2 f) 

fF1 = lift3 f 

fExample1 = apply fF1 [True, True, True] 
fExample2 = apply fF1 [True, False] 
fExample3 = apply (partialApply fF1 [True, False]) [False] 

बेशक

, यदि आप अलग से lift0, lift1, lift2, lift3, आदि को परिभाषित करने के बॉयलरप्लेट पसंद नहीं है, तो आप कुछ एक्सटेंशन को सक्षम करने की जरूरत है। लेकिन आप उनके बिना काफी दूर हो सकते हैं!

यहां बताया गया है कि आप एक lift फ़ंक्शन को सामान्यीकृत कैसे कर सकते हैं। सबसे पहले, हम कुछ मानक प्रकार-स्तर संख्याओं को परिभाषित करते हैं:

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

data Z = Z 
newtype S n = S n 

फिर उठाने के लिए टाइपक्लास प्रस्तुत करें। आपको I n a b को a की प्रतियों के रूप में b "के रूप में पढ़ना चाहिए।

class Lift n a b where 
    type I n a b :: * 
    lift :: n -> I n a b -> ListF a b 

instance Lift Z a b where 
    type I Z a b = b 
    lift _ b = Cons b tooMany 

instance (Lift n a (a -> b), I n a (a -> b) ~ (a -> I n a b)) => Lift (S n) a b where 
    type I (S n) a b = a -> I n a b 
    lift (S n) f = Cons tooFew (lift n f) 

और यहाँ पहले से f, पुनः उपयोग द्वारा सामान्यीकृत लिफ्ट का उपयोग कर उदाहरण है: ठीक है, एक तरह से

fF2 = lift (S (S (S Z))) f 

fExample4 = apply fF2 [True, True, True] 
fExample5 = apply fF2 [True, False] 
fExample6 = apply (partialApply fF2 [True, False]) [False] 

Answer 7

और इनपुट कुछ others की मैं इस लक्ष्य को हासिल करने के लिए एक तरह से परिभाषित साथ

(, एक कस्टम सूची प्रकार के साथ) जो पिछले उत्तरों से थोड़ा अलग है। यह एक पुराना सवाल है, लेकिन ऐसा लगता है कि अभी भी देखा जा रहा है, इसलिए मैं पूर्णता के लिए दृष्टिकोण जोड़ूंगा।

हम एक एक्सटेंशन (जीएडीटी) का उपयोग करते हैं, जिसमें एक सूची प्रकार डैनियल वाग्नेर के समान होता है, लेकिन टैगिंग फ़ंक्शन पेनो नंबर के बजाय टाइपिंग के साथ। चलो टुकड़ों में कोड के माध्यम से चलो। सबसे पहले हम एक्सटेंशन सेट करते हैं और सूची प्रकार को परिभाषित करते हैं। डेटाटाइप पॉलिमॉर्फिक है इसलिए इस फॉर्मूलेशन तर्क में एक ही प्रकार का होना आवश्यक नहीं है।

{-# LANGUAGE GADTs #-} 

-- n represents function type, o represents output type 
data LApp n o where 
    -- no arguments applied (function and output type are the same) 
    End :: LApp o o 
    -- intentional similarity to ($) 
    (:$) :: a -> LApp m o -> LApp (a -> m) o 

infixr 5 :$ -- same as : 

चलिए एक ऐसा फ़ंक्शन परिभाषित करते हैं जो इस तरह की एक सूची ले सकता है और इसे किसी फ़ंक्शन पर लागू कर सकता है। यहां कुछ प्रकार की ट्रिकरी है: फ़ंक्शन में n टाइप किया गया है, listApply पर कॉल केवल तभी संकलित होगा जब यह प्रकार हमारी सूची प्रकार पर n टैग से मेल खाता हो। हमारे आउटपुट प्रकार o को छोड़कर, हम इसमें कुछ स्वतंत्रता छोड़ते हैं (जब सूची बनाते हैं तो हमें तुरंत उस तरह के फ़ंक्शन को ठीक करने की आवश्यकता नहीं होती है जिसे इसे लागू किया जा सकता है)।

-- the apply function 
listApply :: n -> LApp n o -> o 
listApply fun End = fun 
listApply fun (p :$ l) = listApply (fun p) l 

यही है! अब हम अपने सूची प्रकार में संग्रहीत तर्कों के लिए फ़ंक्शंस लागू कर सकते हैं। और अधिक अपेक्षित? :)

-- showing off the power of AppL 
main = do print . listApply reverse $ "yrruC .B lleksaH" :$ End 
      print . listApply (*) $ 1/2 :$ pi :$ End 
      print . listApply ($) $ head :$ [1..] :$ End 
      print $ listApply True End 

दुर्भाग्य से हम तरह की हमारी सूची प्रकार के में बंद कर रहे हैं, हम सिर्फ उन्हें listApply साथ उपयोग करने के लिए सामान्य सूचियों परिवर्तित नहीं कर सकते। मुझे संदेह है कि यह टाइप चेकर के साथ एक मौलिक मुद्दा है (सूची के मूल्य के आधार पर प्रकार समाप्त होते हैं) लेकिन ईमानदार होने के लिए मैं पूरी तरह से सुनिश्चित नहीं हूं।

-- Alternative definition 
-- data FList n o a where 
-- Nil :: FList o o a 
-- Cons :: a -> FList f o a -> FList (a -> f) o a 

यहाँ a, जहां तर्क प्रकार का प्रतिनिधित्व करता है:

-- Can't do this :(
-- listApply (**) $ foldr (:$) End [2, 32] 

आप एक विषम सूची का उपयोग कर के बारे में असहज महसूस करते हैं, तुम सब करने की ज़रूरत LApp प्रकार के लिए एक अतिरिक्त पैरामीटर जोड़ने, जैसे है जिस फ़ंक्शन पर लागू किया गया है उसे भी उसी प्रकार के तर्क स्वीकार करना होगा।

Answer 8

मुझे इस फ़ंक्शन के उपयोग के मामले के बारे में अनिश्चितता है। सूचियां अपरिवर्तनीय हैं और एक समारोह लौटती हैं। यह मुझे लगता है कि जो कुछ भी आपके उपयोग के मामले में इसके लिए एक और अधिक सीधे समाधान होगा। हालांकि मैं निम्नानुसार एक तरीका सुझा सकता हूं;

instance Show (a -> b) where 
    show a = "function" 

apply :: Num a => (a -> a) -> [a] -> (a -> a) 
apply f []  = f 
apply f (x:xs) = apply ((\_ -> f) (f x)) xs 

Answer 9

यह आपके मूल प्रश्न का उत्तर नहीं है, लेकिन मुझे लगता है कि यह आपके उपयोग-मामले का उत्तर हो सकता है।

pure f <*> [arg] <*> [arg2] ... 
-- example 
λ>pure (\a b c -> (a*b)+c) <*> [2,4] <*> [3] <*> [1] 
[7,13] 
λ>pure (+) <*> [1] <*> [2] 
[3] 

सूची के अनुप्रयोगी उदाहरण इस सुपर संकीर्ण यूज-केस हालांकि की तुलना में बहुत व्यापक है ...

λ>pure (+1) <*> [1..10] 
[2,3,4,5,6,7,8,9,10,11] 
-- Or, apply (+1) to items 1 through 10 and collect the results in a list 

λ>pure (+) <*> [1..5] <*> [1..5] 
[2,3,4,5,6,3,4,5,6,7,4,5,6,7,8,5,6,7,8,9,6,7,8,9,10] 

{- The applicative instance of list gives you every possible combination of 
elements from the lists provided, so that is every possible sum of pairs 
between one and five -} 

λ>pure (\a b c -> (a*b)+c) <*> [2,4] <*> [4,3] <*> [1] 
[9,7,17,13] 
{- that's - 2*4+1, 2*3+1, 4*4+1, 4*3+1 
Or, I am repeating argC when I call this function twice, but a and b are 
different -} 
λ>pure (\a b c -> show (a*b) ++ c) <*> [1,2] <*> [3,4] <*> [" look mah, other types"] 
["3 look mah, other types","4 look mah, other types","6 look mah, other types","8 look mah, other types"] 

तो यह इसी अवधारणा नहीं है, ठीक है, लेकिन यह उन compositional का एक बहुत उपयोग मामलों, और कुछ और जोड़ता है।