यह कार्यान्वयन फोल्डेबल टाइपकास्ट का बुरा उदाहरण क्यों है?

Jan 02 2021

मैं अद्भुत हास्केल बुक के माध्यम से काम कर रहा हूं । ट्रैवर्सेबल अध्याय (21) के अंत में, मुझे निम्नलिखित ट्री के लिए एक उदाहरण लिखने की आवश्यकता है:

data Tree a =
    Empty
  | Leaf a
  | Node (Tree a) a (Tree a)

यहाँ मेरे समाधान के पूर्ण कोड के लिए एक लिंक है । अभ्यास दोनों को लागू करने की कोशिश करने की सिफारिश करता है foldMapऔर foldr। यह है कि मैंने कैसे लागू किया foldr(आह्वान आदेश में ज्यादा विचार किए बिना):

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  f x $ foldr f (foldr f z left) right

मैंने तब foldMapनिम्न प्रकार से लागू किया:

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

जब मैं क्विकचेक का foldableपरीक्षण बैच चलाता हूं , तो मुझे कुछ विफलताएं मिलती हैं। foldrनिम्नलिखित के लिए मेरे कार्यान्वयन को बदलने से सभी परीक्षण पास हो जाते हैं:

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  foldr f (f x (foldr f z right)) left

मैंने अपने दम पर असफल परीक्षा का मामला चलाने की कोशिश की, लेकिन असफलता को फिर से नहीं बना सका:

*Ch21_12_ExercisesTree Data.Monoid> tree = Node (Node (Leaf (-5)) 3 (Node (Leaf 3) 5 Empty)) (-2) Empty
*Ch21_12_ExercisesTree Data.Monoid> foldr (<>) (mempty :: Sum Int) t
Sum {getSum = 4}
*Ch21_12_ExercisesTree Data.Monoid> foldMap Sum t
Sum {getSum = 4}

मुझे संदेह है कि कुछ ऐसा है जो foldआईएनजी फ़ंक्शन के बारे में पता नहीं लगा रहा है जो क्विकचेक का उपयोग कर रहा है।

प्रशन:

असफलताएँ क्यों होती हैं?
क्विकचेक द्वारा परीक्षण में उपयोग किए जाने वाले फ़ंक्शन को प्राप्त करने का एक तरीका है?

जवाब

4 duplode Jan 02 2021 at 06:30

foldrफ़ंक्शन का मान बदलकर (मोनॉयडली) हो सकने वाले फ़ंक्शन में , मोनॉइड foldMap का उपयोग करकेEndo प्राप्त किया जा सकता है। ऐसा होने पर, यदि आपका ...a -> b -> bab -> bfoldMap

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

... संगत foldrहोना चाहिए:

foldr f z Empty = id z  -- mempty amounts to id
foldr f z (Leaf x) = (f x) z
foldr f z (Node left x right) = 
  ((\e -> foldr f e left) . f x . (\e -> foldr f e right)) z  -- (<>) amounts to (.)

अगर हम थोड़ा ठीक है ...

foldr f z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  foldr f (f x (foldr f z right)) left)

... हमें foldrआपके प्रश्न में लिखी गई सही परिभाषा मिलती है । जैसा कि कार्यान्वयन के बीच के अंतर को रचना के क्रम के साथ करना पड़ता है, एक गैर-कम्यूटेटिव मोनॉइड को आसानी से आज़माने से मामला विफल हो जाता है, जैसा कि आपको पता चला है ।

क्विकचेक उपमहाद्वीप पर, मैं डीडीब के जवाब को टालता हूं । ।

3 DDub Jan 02 2021 at 05:40

जैसा कि आप पहले ही काट चुके हैं, इसका कारण यह है कि आप विफल हो रहे हैं क्योंकि दो कार्यान्वयन अलग-अलग हैं, जिन्हें आप गैर-कम्यूटेटिव मोनॉइड का उपयोग करके देख सकते हैं।

क्विकचेक द्वारा उपयोग किए जाने वाले फ़ंक्शन को प्राप्त करना इतना सरल नहीं है। उदाहरण के लिए, यह प्रश्न /Show क्विक चेक द्वारा उत्पन्न कार्यों के बारे में थोड़ा और जानकारी के लिए उत्तर देता है।

जिस तरह से प्राप्त करने के लिए ShowQuickCheck से बाहर सक्षम कार्यों में समारोह रैप करने के लिए है प्रकार । उस ने कहा, जिस कोड को आप कॉल कर रहे हैं ( यहां पाया गया है ) बस सीधे फ़ंक्शन का उपयोग करता है, इसलिए उन्हें कभी नहीं दिखाया जा सकता है। एक विकल्प जिसे आप आज़मा सकते हैं, वह फ़ंक्शन का अपना संस्करण बनाना है जहां आप फ़ंक्शन को लागू करने के लिए जगह के रूप में और आवश्यक के रूप में उपयोग करते हैं ।FunfoldableFun a ba -> bapplyFun

2 javinor Jan 02 2021 at 03:00

मुझे बस एहसास हुआ कि मैंने एक कम्यूटेटिव मोनॉइड का उपयोग किया है ... मैं एक गैर-कम्यूटेटिव मोनॉयड का उपयोग करके विफलता को फिर से बनाने में सक्षम था:

> ftree = fmap (First . Just) tree
> foldr (<>) mempty ft
First {getFirst = Just (-2)}
> foldMap (First . Just) ft
First {getFirst = Just (First {getFirst = Just (-5)})}

यह शायद एक साधारण मामला है। मुझे लगता है कि वास्तविक डेटा प्रकारों के साथ उत्पादन कोड में यह बहुत अधिक जटिल हो सकता है।