تنفيذ الرمز البريدي باستخدام Foldr

Question

أنا حاليًا في الفصل الرابع من Real World Haskell، وأحاول أن أستوعب الأمر تنفيذ Foldl من حيث Foldr.

(وهذا هو الكود الخاص بهم :)

myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

اعتقدت أنني سأحاول التنفيذ zip باستخدام نفس التقنية، ولكن لا يبدو أنني أحرز أي تقدم.هل هذا ممكن حتى؟

Answer 1

zip2 xs ys = foldr step done xs ys
  where done ys = []
        step x zipsfn []     = []
        step x zipsfn (y:ys) = (x, y) : (zipsfn ys)

وكيف يعمل هذا: (الخطوة foldr القيام به XS) إرجاع الوظيفة التي تستهلك يس. حتى نذهب إلى أسفل القائمة XS بناء على تركيبة متداخلة من الوظائف التي سيتم تطبيقها كل على الجزء المقابل من يس.

وكيفية الخروج معها: لقد بدأت مع الفكرة العامة (من تشبه أمثلة له مثيل من قبل)، كتب

zip2 xs ys = foldr step done xs ys

وشغل بعد ذلك في كل من الأسطر التالية بدوره مع ما كان ل يكون لجعل أنواع والقيم يخرج الحق. وكان أسهل ل النظر في أبسط الحالات لأول مرة أمام أصعب منها.

ويمكن أن تكون مكتوبة السطر الأول أكثر ببساطة ك

zip2 = foldr step done

وكما أظهرت mattiast.

Answer 2

لقد سبق أن قدمنا ​​الجواب هنا، ولكن ليس اشتقاقاً (توضيحياً).لذلك، حتى بعد كل هذه السنوات، ربما يكون من المفيد إضافتها.

انها في الواقع بسيطة جدا.أولاً،

foldr f z xs 
   = foldr f z [x1,x2,x3,...,xn] = f x1 (المجلد f z [x2,x3,...,xn])
   = ... = f x1 (و ×2 (و ×3 (...(و xن ض) ...)))

ومن ثم عن طريق التوسع ايتا،

foldr f z xs ys
   = foldr f z [x1,x2,x3,...,xn] ys = f x1 (foldr f z [x2,x3,...,xn]) ys
   = ... = f x1 (و ×2 (و ×3 (...(و xن ض) ...))) ys

وكما هو واضح هنا، لو f غير مؤثر في الوسيطة الثانية, ، يبدأ العمل أولاً على x1 و ys, f x1r1ys أين r1 =(f x2 (f x3 (... (f xn z) ...)))= foldr f z [x2,x3,...,xn].

لذلك، باستخدام

f x1 ص1 [] = []
f x1 ص1 (y1:ys1) = (x1,y1) : ص1 ys1

نحن نرتب لمرور المعلومات من اليسار إلى اليمين على طول القائمة، بواسطة الاتصال r1 مع ال استراحة من قائمة الإدخال ys1, foldr f z [x2,x3,...,xn]ys1 = f x2r2ys1, ، كخطوة تالية.وهذا هو الذي.

---

متى ys أقصر من xs (أو بنفس الطول). [] حالة ل f الحرائق وتوقف المعالجة.لكن اذا ys اطول من xs ثم f'س [] القضية لن تنطلق وسنصل إلى النهائي f xnz(yn:ysn) طلب،

f xn ض (yn:ysn) = (xn,yn) : ض ysn

منذ أن وصلنا إلى نهاية xs, ، ال zip يجب أن تتوقف المعالجة:

ض _ = []

وهذا يعني التعريف z = const [] يجب أن تستخدم:

zip xs ys = foldr f (const []) xs ys
  where
    f x r []     = []
    f x r (y:ys) = (x,y) : r ys

من وجهة نظر f, r يلعب دور أ استمرار النجاح, ، أيّ f يستدعي عند استمرار المعالجة، بعد إصدار الزوج (x,y).

لذا r يكون "ما يتم مع المزيد ys عندما يكون هناك المزيد xس", ، و z = const [], ، ال nil-حالة في foldr, ، يكون "ما يتم به ys عندما لا يكون هناك المزيد xس".أو f يمكن أن تتوقف من تلقاء نفسها، والعودة [] متى ys تم استنفاد.

---

لاحظ كيف ys يتم استخدامه كنوع من القيمة المتراكمة، والتي يتم تمريرها من اليسار إلى اليمين على طول القائمة xs, ، من استدعاء واحد ل f إلى الخطوة التالية ("التراكمية" هي تجريد عنصر الرأس منه).

بطبيعة الحال وهذا يتوافق مع الطية اليسرى، حيث الخطوة المتراكمة هي "تطبيق الوظيفة"، مع z = id إرجاع القيمة المتراكمة النهائية عندما "لا يوجد المزيد xس":

foldl f a xs =~ foldr (\x r a-> r (f a x)) id xs a

وبالمثل، بالنسبة للقوائم المحدودة،

foldr f a xs =~ foldl (\r x a-> r (f x a)) id xs a

وبما أن وظيفة الدمج هي التي تقرر ما إذا كانت ستستمر أم لا، فمن الممكن الآن أن يكون لديك طية أيسر يمكن أن تتوقف مبكرًا:

foldlWhile t f a xs = foldr cons id xs a
  where 
    cons x r a = if t x then r (f a x) else a

أو تخطي الطية اليسرى، foldlWhen t ..., ، مع

    cons x r a = if t x then r (f a x) else r a

إلخ.

Answer 3

ولقد وجدت طريقة استخدام طريقة مماثلة تماما للك:

myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
    where step a f (b:bs) = (a,b):(f bs)
          step a f [] = []

Answer 4

لوHaskellers غير أصلية هنا، لقد كتبت نسخة مخطط هذه الخوارزمية لجعله أكثر وضوحا ما يحدث في الواقع:

> (define (zip lista listb)
    ((foldr (lambda (el func)
           (lambda (a)
             (if (empty? a)
                 empty
                 (cons (cons el (first a)) (func (rest a))))))
         (lambda (a) empty)
         lista) listb))
> (zip '(1 2 3 4) '(5 6 7 8))
(list (cons 1 5) (cons 2 6) (cons 3 7) (cons 4 8))

والنتائج foldr في وظيفة والتي عند تطبيقها على القائمة، سيعود الرمز البريدي للقائمة مطوية على مع قائمة معينة إلى وظيفة. وهاسكل يخفي lambda الداخلية لتقييم كسول.

---

لكسر عليه قائلا:

وتأخذ الرمز البريدي على المدخلات: '(1 2 3) يحصل يسمى ظائفها foldr مع

el->3, func->(lambda (a) empty)

وهذا يوسع إلى:

(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a))))

إذا كان لنا أن العودة هذا الآن، سيكون لدينا وظيفة والتي تأخذ قائمة عنصر واحد ويعود الزوج (3 عنصر):

> (define f (lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a)))))
> (f (list 9))
(list (cons 3 9))

والمستمر، foldr يدعو الآن ظائفها مع

el->3, func->f ;using f for shorthand
(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

وهذا هو ظائفها التي تأخذ قائمة مع اثنين من العناصر، الآن، والكود البريديه لهم (list 2 3):

> (define g (lambda (a) (cons (cons 2 (first a)) (f (rest a)))))
> (g (list 9 1))
(list (cons 2 9) (cons 3 1))

وماذا يحدث؟

(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

وa، في هذه الحالة، يتم (list 9 1)

(cons (cons 2 (first (list 9 1))) (f (rest (list 9 1))))
(cons (cons 2 9) (f (list 1)))

وكما تذكرون، f الكود البريديه حجتها مع 3.

واستمر هذا الوضع الخ ...

Answer 5

والمشكلة مع كل هذه الحلول لzip هي أنها أضعاف فقط أكثر من قائمة أو أخرى، والتي يمكن أن يكون مشكلة إذا كان كل منهم "المنتجين جيد"، في لغة من قائمة الانصهار. ما تحتاجه فعلا هو الحل الذي تطوي على كلا القائمتين. لحسن الحظ، هناك ورقة حول بالضبط، ودعا "Coroutining طيات مع Hyperfunctions" .

وتحتاج إلى نوع المساعدة، وفرط الوظيفة، التي هي في الأساس وظيفة التي تأخذ فرط الوظيفة آخر كما حجتها.

newtype H a b = H { invoke :: H b a -> b }

ووhyperfunctions المستخدمة هنا تعمل أساسا مثل "كومة" من الوظائف العادية.

push :: (a -> b) -> H a b -> H a b
push f q = H $ \k -> f $ invoke k q

وأنت أيضا بحاجة إلى وسيلة لوضع اثنين معا hyperfunctions، نهاية لهذه الغاية.

(.#.) :: H b c -> H a b -> H a c
f .#. g = H $ \k -> invoke f $ g .#. k

وهذا مرتبط push بالقانون:

(push f x) .#. (push g y) = push (f . g) (x .#. y)

وهذا تبين أن عامل النقابي، وهذه هي الهوية:

self :: H a a
self = H $ \k -> invoke k self

وأنت أيضا بحاجة إلى شيء أن يتجاهل كل شيء آخر على "كومة" وإرجاع قيمة معينة:

base :: b -> H a b
base b = H $ const b

وأخيرا، تحتاج إلى وسيلة للحصول على قيمة للخروج من فرط الوظيفة:

run :: H a a -> a
run q = invoke q self

وسلاسل run جميع وظائف pushed معا، نهاية إلى نهاية، حتى يضرب base أو حلقات ما لا نهاية.

وحتى الآن يمكنك أضعاف كلتا القائمتين في hyperfunctions، وذلك باستخدام المهام التي تمرير المعلومات من واحد إلى آخر، وتجميع القيمة النهائية.

zip xs ys = run $ foldr (\x h -> push (first x) h) (base []) xs .#. foldr (\y h -> push (second y) h) (base Nothing) ys where
  first _ Nothing = []
  first x (Just (y, xys)) = (x, y):xys

  second y xys = Just (y, xys)

والسبب للطي على كل المسائل القوائم هو بسبب شيء GHC لا يسمى بالقائمة <م> الانصهار ، التي تحدثت عنها في <لأ href = "http://hackage.haskell.org/package/ قاعدة 4.9.0.0 / مستندات / SRC / GHC.Base.html # بناء "يختلط =" noreferrer "> وحدة GHC.Base ، ولكن ربما ينبغي أن يكون أكثر من ذلك بكثير معروفة. كونها جيدة منتج القائمة واستخدام build مع foldr يمكن أن يمنع الكثير من الانتاج عديمة الفائدة والاستهلاك الفوري لعناصر القائمة، ويمكن أن يعرض المزيد من التحسينات.

Answer 6

وحاولت أن أفهم هذا الحل أنيقة نفسي، لذلك حاولت أن تستمد أنواع وتقييم نفسي. لذلك، نحن بحاجة إلى كتابة دالة:

zip xs ys = foldr step done xs ys

وهنا نحن بحاجة إلى استخلاص step وdone، مهما كانت. أذكر foldr الصورة نوع، مثيل للقوائم:

foldr :: (a -> state -> state) -> state -> [a] -> state

ولكن لدينا الاحتجاج foldr يجب مثيل لشيء من هذا القبيل أدناه، لأننا يجب أن تقبل يست واحدة، ولكن اثنين من الحجج القائمة:

foldr :: (a -> ? -> ?) -> ? -> [a] -> [b] -> [(a,b)]

ولأن -> هو بزر الماوس الأيمن النقابي ، و هذا هو ما يعادل:

foldr :: (a -> ? -> ?) -> ? -> [a] -> ([b] -> [(a,b)])

ولدينا ([b] -> [(a,b)]) يتوافق مع state نوع متغير في الأصلي التوقيع نوع foldr، لذلك يجب علينا استبدال كل تواجد state معها:

foldr :: (a -> ([b] -> [(a,b)]) -> ([b] -> [(a,b)]))
      -> ([b] -> [(a,b)])
      -> [a]
      -> ([b] -> [(a,b)])

وهذا يعني أن الحجج التي نعبر إلى foldr يجب أن يكون الأنواع التالية:

step :: a -> ([b] -> [(a,b)]) -> [b] -> [(a,b)]
done :: [b] -> [(a,b)]
xs :: [a]
ys :: [b]

ويذكر أن foldr (+) 0 [1,2,3] تتسع ل:

1 + (2 + (3 + 0))

وذلك إذا xs = [1,2,3] وys = [4,5,6,7]، لدينا الاحتجاج foldr ستتوسع إلى:

1 `step` (2 `step` (3 `step` done)) $ [4,5,6,7]

وهذا يعني أن لدينا بناء 1 `step` (2 `step` (3 `step` done)) يجب إنشاء وظيفة العودية التي من شأنها أن تذهب من خلال [4,5,6,7] وزمم العناصر. (نضع في اعتبارنا، أنه إذا كان أحد من القوائم الأصلية أطول، يتم طرح القيم الزائدة بعيدا). IOW، يجب أن يكون لدينا بناء نوع [b] -> [(a,b)].

و3 `step` done هي حالتنا قاعدة، حيث done هو القيمة الأولية، مثل 0 في foldr (+) 0 [1..3]. نحن لا نريد لالبريدي أي شيء بعد 3 لأن 3 هو القيمة النهائية للxs، لذلك يجب علينا إنهاء العودية. كيف يمكن إنهاء العودية على القائمة في الحالة الأساسية؟ يمكنك العودة قائمة فارغة []. ولكن نوع استدعاء done التوقيع:

done :: [b] -> [(a,b)]

لذلك لا يمكننا العودة فقط []، يجب أن نعود وظيفة التي من شأنها أن نتجاهل أيا كان يحصل عليه. ولذلك استخدام const :

done = const [] -- this is equivalent to done = \_ -> []

والآن لنبدأ في معرفة ما step ينبغي أن يكون. فهو يجمع بين قيمة من نوع a مع وظيفة من نوع [b] -> [(a,b)] وإرجاع وظيفة من نوع [b] -> [(a,b)].

في 3 `step` done، ونحن نعلم أن قيمة نتيجة من شأنها أن تذهب في وقت لاحق الى قائمة مضغوط لدينا يجب (3,6) (معرفة من xs الأصلي وys). لذلك يجب 3 `step` done تقييم إلى:

\(y:ys) -> (3,y) : done ys

وتذكر، يجب أن نعود وظيفة، داخل الذي نحن البريدي بطريقة أو بأخرى حتى العناصر، رمز أعلاه هو ما يجعل المعنى وtypechecks.

والآن بعد أن افترضنا بالضبط كيف step يجب تقييم، دعونا مواصلة التقييم. وهنا كيف تبدو جميع خطوات التخفيض في تقييم foldr لدينا مثل:

3 `step` done -- becomes
(\(y:ys) -> (3,y) : done ys)
2 `step` (\(y:ys) -> (3,y) : done ys) -- becomes
(\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys)
1 `step` (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) -- becomes
(\(y:ys) -> (1,y) : (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) ys)

والتقييم يثير هذا تنفيذ خطوة (لاحظ أن نفسر ys ينفد من العناصر في وقت مبكر عن طريق إرجاع قائمة فارغة):

step x f = \[] -> []
step x f = \(y:ys) -> (x,y) : f ys

وهكذا، يتم تنفيذ zip وظيفة كاملة كما يلي:

zip :: [a] -> [b] -> [(a,b)]
zip xs ys = foldr step done xs ys
  where done = const []
        step x f [] = []
        step x f (y:ys) = (x,y) : f ys

وPS: إذا كنت مستوحاة من أناقة طيات، وقراءة <م> الكتابة foldl باستخدام foldr ثم غراهام هاتون <م> وهناك أمثلة توضيحية على عالمية والقدرة على التعبير من أمثال .

Answer 7

ونهج بسيط:

lZip, rZip :: Foldable t => [b] -> t a -> [(a, b)]

-- implement zip using fold?
lZip xs ys = reverse.fst $ foldl f ([],xs) ys
     where f  (zs, (y:ys)) x = ((x,y):zs, ys)

-- Or;
rZip xs ys = fst $ foldr f ([],reverse xs) ys
     where f x (zs, (y:ys))  = ((x,y):zs, ys)