हास्केल

Question

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

lastJustM :: (Monad m) => (a -> m (Maybe a)) -> a -> m a 
lastJustM g x = g x >>= maybe (return x) (lastJustM g) 

हास्केल में मेरी स्वयं शिक्षा के हिस्से के रूप में मैं स्पष्ट प्रत्यावर्तन से बचने के लिए कोशिश कर रहा हूँ (या कम से कम कैसे समझ में) जब भी मैं कर सकते हैं। ऐसा लगता है कि इस मामले में एक साधारण गैर-स्पष्ट रूप से रिकर्सिव समाधान होना चाहिए, लेकिन मुझे इसे समझने में परेशानी हो रही है।

मुझे a monadic versiontakeWhile की तरह कुछ नहीं चाहिए, क्योंकि यह सभी पूर्व-कुछ मूल्यों को इकट्ठा करने के लिए महंगा हो सकता है, और मुझे उनकी परवाह नहीं है।

मैंने हस्ताक्षर के लिए होगल की जांच की और कुछ भी दिखाई नहीं देता है। m (Maybe a) बिट मुझे लगता है कि एक मोनैड ट्रांसफॉर्मर यहां उपयोगी हो सकता है, लेकिन मेरे पास वास्तव में अंतर्ज्ञान नहीं है जो मुझे विवरण (अभी तक) के साथ आने की आवश्यकता होगी।

शायद यह करने के लिए शर्मनाक रूप से आसान है या यह देखने में शर्मनाक रूप से आसान है कि यह क्यों नहीं किया जा सकता है या नहीं किया जाना चाहिए, लेकिन यह पहली बार नहीं होगा जब मैंने शैक्षणिक रणनीति के रूप में आत्म-शर्मिंदगी का उपयोग किया हो।

अद्यतन: मैं निश्चित रूप से बजाय Maybe उपयोग करने का एक विधेय प्रदान कर सकता है: (a -> Bool) -> (a -> m a) -> a की तरह कुछ (अंतिम मान जिसके लिए विधेय सच है लौटने) बस के रूप में अच्छी तरह से काम करेगा। मुझे जो दिलचस्पी है वह मानक संयोजकों का उपयोग करके स्पष्ट रिकर्सन के बिना संस्करण लिखने का एक तरीका है।

---

पृष्ठभूमि: यहाँ संदर्भ के लिए एक सरल काम कर उदाहरण है: मान लीजिए हम इकाई वर्ग में यादृच्छिक क्षेत्रों में रुचि रखते हैं, लेकिन हम केवल बाहर निकलने के बिंदु के बारे में परवाह।

randomStep :: (Floating a, Ord a, Random a) => 
       a -> (a, a) -> State StdGen (Maybe (a, a)) 
randomStep s (x, y) = do 
    (a, gen') <- randomR (0, 2 * pi) <$> get 
    put gen' 
    let (x', y') = (x + s * cos a, y + s * sin a) 
    if x' < 0 || x' > 1 || y' < 0 || y' > 1 
    then return Nothing 
    else return $ Just (x', y') 

कुछ evalState (lastJustM (randomStep 0.01) (0.5, 0.5)) <$> newStdGen की तरह हमें एक नया डेटा बिंदु दे देंगे: हम निम्नलिखित कदम समारोह है।

Answer 1

स्पष्ट रिकर्सन से बचने के बारे में बहुत कुछ है जो अंतर्निहित रिकर्सिव combinators लिख रहा है, जो आम तौर पर बहुत सामान्य अनलिमिटेड मूल्यों पर काम करते हैं। एक फंक्टर, मोनाड, या अन्य उठाए गए प्रकार में एक ही काम करना कभी-कभी मूल उठाने के संचालन जैसे fmap, <*>, >>=, और इसी तरह से काम करता है। कुछ मामलों में एक पूर्व-उठाया संस्करण पहले से मौजूद है, जैसे mapM, zipWithM, और इसी तरह। अन्य बार, takeWhile के साथ, उठाना छोटा नहीं है और कोई अंतर्निहित संस्करण प्रदान नहीं किया गया है।

आपके फ़ंक्शन में वास्तव में कुछ ऐसी विशेषताएं हैं जो मानक संयोजकों का एक उठाया संस्करण होना चाहिए। तो सबसे पहले, के समारोह का पुनर्निर्माण करने के आप परोक्ष उठाने रहे हैं इकाई को निकाल देते हैं:

lastJust :: (a -> Maybe a) -> a -> a 

शब्द "पिछले" यहां हमें एक संकेत देता है; गैर-स्पष्ट रिकर्सन अक्सर नियंत्रण संरचनाओं के रूप में अस्थायी सूचियों का उपयोग करता है। तो आप क्या चाहते हैं lastNothing प्राप्त करने तक फ़ंक्शन को पुन: उत्पन्न करके उत्पन्न सूची में लागू किया गया है।क्योंकि (मेरी जानकारी के लिए, इस बिंदु हम एक तरह से समस्या आ रही पर

dup x = (x, x) 
lastJust f x = last $ unfoldr (fmap dup . f) x 

दुर्भाग्य:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 

तो हम कुछ इस तरह है: प्रकार के एक मामूली सामान्यीकरण के साथ, हम जनरेटर लगता है) कोई मोनैडिक खुलासा नहीं है और इसे उठाना takeWhile है, जो तुच्छ नहीं है। एक और चीज जो समझ में आ सकती है, (MonadMaybe m) => (b -> m (a, b)) -> b -> m [a] और MaybeT ट्रांसफॉर्मर के साथ हस्ताक्षर के साथ अधिक सामान्य रूप से सामने आती है, लेकिन यह मानक पुस्तकालयों में मौजूद नहीं है, और मोनैड ट्रांसफार्मर वैसे भी निराशाजनक पिट की तरह हैं। Maybe और MonadPlus या कुछ समान के रूप में अज्ञात मोनैड को सामान्यीकृत करने का कोई तरीका ढूंढने का एक तीसरा दृष्टिकोण हो सकता है।

बेशक, एक अलग संरचना के साथ अन्य दृष्टिकोण भी हो सकते हैं, लेकिन मुझे संदेह है कि आपको किसी भी कार्य के साथ समान अजीबता मिल सकती है जिसे एक मोनैड में "घुमाने" की आवश्यकता होती है, उदाहरण के लिए, प्रत्येक चरण अवधारणात्मक रूप से दूसरे को पेश करता है परत है कि >>=, join के साथ समाप्त किया जाना चाहिए, आदि

सारांश में: पहले निरीक्षण अपने कार्य के रूप में लिखा सबसे अच्छा स्पष्ट प्रत्यावर्तन के बिना व्यक्त किया जाता है, एक पुनरावर्ती Combinator (unfoldM के कुछ स्वाद) का उपयोग पर मौजूद नहीं है। आप या तो खुद को संयोजक लिख सकते हैं (जैसा कि लोगों ने takeWhileM के साथ किया है), मोनैडिक रिकर्सिव संयोजकों के लिए हैकेज पर खुदाई करें, या बस अपना कोड छोड़ दें।

Answer 2

मैं takeWhile के monadic संस्करण कुछ इस नहीं करना चाहती, क्योंकि यह सभी पूर्व कुछ भी नहीं मान एकत्र करने के महंगा हो सकता है, और मैं उनके बारे में वैसे भी परवाह नहीं है। जब तक आप स्पष्ट है कि क्या करना चाहते हैं

Monadic सूचियों takeWhile सभी पूर्व कुछ भी नहीं मान एकत्रित नहीं करता। यह "List" package से takeWhile होगा, जो आपके द्वारा लिंक किए गए प्रश्न के लिए this answer में उपयोग किया गया है।

समारोह है कि आप को लागू करना चाहते हैं के लिए के रूप में:

{-# LANGUAGE ScopedTypeVariables #-} 

import Control.Monad.ListT (ListT) -- from "List" package on hackage 
import Data.List.Class (takeWhile, iterateM, lastL) 
import Prelude hiding (takeWhile) 

thingM :: forall a m. Monad m => (a -> Bool) -> (a -> m a) -> m a -> m a 
thingM pred stepM startM = 
    lastL $ takeWhile pred list 
    where 
     list :: ListT m a 
     list = iterateM stepM startM