'पूंछ'

Question

की रिकर्सन-स्कीम सामान्यीकरण मुझे एक रिकर्सन-स्कीम शैली संरचना मिल गई है और मैं पूर्ण संरचना समेत सभी संरचनाओं की एक सूची प्राप्त करना चाहता हूं - यानी tails फ़ंक्शन List पर फ़ंक्शन करता है । मुझे लगता है कि para पर कॉल करके इसे लागू करना संभव होगा, प्रत्येक चरण में मूल संरचना पर वापस मैप करना होगा, और उसके बाद मूल संरचना को अलग से चिपकाएं, लेकिन यह बहुत बोझिल लगता है: (अवांछित, मास्कल अगर मास्कल गलत है; एक सामान्यीकरण) Mu के संदर्भ में लिखा के रूप में मैं वास्तव में Base निर्माण अभी तक)

gtails :: Functor f => Mu f -> [Mu f] 
gtails = para (\a -> (fmap fst a) : (foldMap snd a)) 

(यानी मामला f=Prim में यह है tails समझा नहीं जा सका है, अन्य f के लिए इतना ही

वहाँ एक अच्छा तरीका है ? मुझे एहसास है कि यह इतना बुरा नहीं है, लेकिन fmap fst a उस चरण में "मूल" संरचना को पुनर्प्राप्त करने के लिए काफी बोझिल लगता है, और foldMap snd a कुछ ऐसा है जो मुझे para (fold a का उपयोग करते समय का उपयोग करते समय बहुत कुछ दोहराता है जो फिर से लगता है यह अनावश्यक होना चाहिए)।

Answer 1

मुझे para के साथ कोई समस्या नहीं दिख रही है। ,

para :: (a -> [a] -> b -> b) -> b -> [a] -> b 
para f z []  = z 
para f z (a:as) = f a as (para f z as) 

tails :: [a] -> [[a]] 
tails = para (\a as res -> (a : as) : res) [[]] 

हालांकि, अगर आप अधिक सामान्य होना चाहते हैं: बस सिर और प्रत्येक Cons कदम पर पूंछ वापस नुकसान:

import Data.Functor.Foldable 

tails :: [a] -> [[a]] 
tails = para (\case Nil -> [[]]; Cons a (as, res) -> (a : as) : res) 

स्पष्टता के लिए, विशेष सूची में और recursion-schemes बिना कम अच्छा para तैयार करने काम आता है:

import qualified Data.Functor.Foldable as Rec (Foldable) 

tails :: (Rec.Foldable t, Base t ~ Prim [a]) => t -> [t] 
tails as = as : para (\case Nil -> []; Cons a (as, res) -> as : res) as 

यह हमेशा की तरह सूचियों के लिए काम करता है, लेकिन आप यह भी type instance Base t = Prim [a] दे सकते हैं अन्य t -s के साथ, Foldable उदाहरण के साथ, और उनका भी उपयोग करें।

tails' :: (Unfoldable t, Rec.Foldable t, Base t ~ Prim [a]) => t -> [t] 
tails' = para (\case Nil -> [embed Nil]; Cons a (as, res) -> embed (Cons a as) : res) 

इस के बाद से प्रत्येक project के लिए वहाँ functors के fixpoints के लिए एक व्युत्क्रम embed होना चाहिए, बहुत बुरा नहीं है:

वैकल्पिक रूप से, हम एक बाधा को शुरू करने की कीमत पर पहले tails परिभाषा रख सकते वैसे भी, Foldable और उदाहरण स्वाभाविक रूप से जोड़ों में आते हैं।

Answer 2

para वास्तव में यहां उपयोग करने का सही कार्य है। मैंने सबकुछ self-contained gist में उदाहरणों के साथ बढ़ाया है यदि आप इसके साथ खेलना चाहते हैं।

हम फिक्सपॉइंट Mu और सामान्य fold और para की परिभाषा से शुरू करते हैं।

tails :: (Functor f, Foldable f) => Mu f -> [Mu f] 
tails m = m : para (foldMap $ uncurry $ flip (:)) m