كيف يعمل Data.MemoCombinators؟

Question

لقد كنت أبحث في المصدر ل Data.MemoCombinators لكني لا أستطيع أن أرى حقًا أين يوجد قلبها.

من فضلك اشرح لي ما هو المنطق وراء كل هذه المجمعات و الميكانيكا لكيفية عملهم فعليًا لتسريع برنامجك في برمجة العالم الحقيقي.

أنا أبحث عن تفاصيل ل هذا التنفيذ، والمقارنة/التباين اختياريًا مع أساليب هاسكل الأخرى في الحفظ.أنا أفهم ما هو الحفظ وأنا لا تبحث عن وصف لكيفية عمله بشكل عام.

Answer 1

هذه المكتبة هي واضحة combinatorization من تقنية معروفة من التحفيظ.دعونا نبدأ مع الكنسي على سبيل المثال:

fib = (map fib' [0..] !!)
    where
    fib' 0 = 0
    fib' 1 = 1
    fib' n = fib (n-1) + fib (n-2)

لقد تفسير ما قلته يعني أن تعرف كيف يعمل هذا.لذلك سوف نركز على combinatorization.

نحن essentiallly يحاول التقاط تعميم فكرة (map f [0..] !!).نوع من هذه الوظيفة (Int -> r) -> (Int -> r), وهذا منطقي:فإنه يأخذ وظيفة من Int -> r وإرجاع memoized نسخة من نفس الوظيفة.أي وظيفة التي لغويا هوية و هذا النوع يسمى "memoizer على Int"(حتى id, التي لا memoize).نحن التعميم إلى هذا التجريد:

type Memo a = forall r. (a -> r) -> (a -> r)

لذلك Memo a, ، memoizer على a, يأخذ وظيفة من a إلى أي شيء ، وإرجاع لغويا متطابقة وظيفة التي تم memoized (أو لا).

فكرة مختلفة memoizers هو العثور على طريقة تعداد المجال مع بنية البيانات ، خريطة الدالة عليها ، ثم مؤشر بنية البيانات. bool مثال جيد:

bool :: Memo Bool
bool f = table (f True, f False)
    where
    table (t,f) True = t
    table (t,f) False = f

وظائف من Bool تعادل أزواج ، باستثناء زوج فقط تقييم كل عنصر مرة واحدة (كما هو حال كل القيمة التي تحدث خارج امدا).لذلك نحن فقط خريطة زوج والظهر.النقطة الأساسية هي أننا رفع تقييم وظيفة فوق امدا عن الحجة (هنا آخر حجة table) حسب تعداد المجال.

Memoizing Maybe a هو قصة مشابهة ، إلا الآن نحن بحاجة إلى معرفة كيفية memoize a عن Just القضية.حتى memoizer على Maybe يأخذ memoizer على a حجة:

maybe :: Memo a -> Memo (Maybe a)
maybe ma f = table (f Nothing, ma (f . Just))
    where
    table (n,j) Nothing = n
    table (n,j) (Just x) = j x

بقية المكتبة فقط الاختلافات حول هذا الموضوع.

طريقة memoizes لا يتجزأ من أنواع يستخدم أكثر ملاءمة هيكل من [0..].انها قليلا المعنية ، ولكن في الأساس مجرد يخلق لا حصر له شجرة (تمثل الأرقام الثنائية إلى توضيح الهيكل):

1
  10
    100
      1000
      1001
    101
      1010
      1011
  11
    110
      1100
      1101
    111
      1110
      1111

بحيث يبحث عددا في الشجرة إدارة الوقت يتناسب مع عدد البتات في تمثيلها.

كما sclv ، كونال هو MemoTrie المكتبة يستخدم نفس الكامنة تقنية, ولكن يستخدم typeclass العرض بدلا من combinator العرض.نشرنا لدينا المكتبات بشكل مستقل في نفس الوقت (في الواقع ، في غضون بضع ساعات!).كونال هو أسهل للاستخدام في الحالات البسيطة (لا يوجد سوى وظيفة واحدة ، memo, وسوف تحدد مذكرة هيكل إلى استخدام على أساس نوع) ، في حين أن الألغام هي أكثر مرونة, كما يمكنك أن تفعل أشياء من هذا القبيل:

boundedMemo :: Integer -> Memo Integer
boundedMemo bound f = \z -> if z < bound then memof z else f z
   where
   memof = integral f

فقط memoizes القيم أقل من معين لا بد اللازمة لتنفيذ أحد المشاريع يولر المشاكل.

وهناك مناهج أخرى ، على سبيل المثال تعريض مفتوح fixpoint الدالة على الكائن الدقيق الاحادي الخلية:

memo :: MonadState ... m => ((Integer -> m r) -> (Integer -> m r)) -> m (Integer -> m r)

مما يتيح المزيد من المرونة ، على سبيل المثال.تطهير مخابئ ، LRU ، إلخ.ولكن الألم في المؤخرة للاستخدام ، كما أنه يضع صرامة القيود على وظيفة أن يكون memoized (مثلا ، لا لا حصر له ترك العودية).أنا لا أعتقد أن هناك أي مكتبات تنفيذ هذه التقنية.

هل هذا الجواب ما كنت غريبة عنه ؟ إن لم يكن, ربما نوضح نقطة كنت في حيرة ؟

Answer 2

القلب هو bits وظيفة:

-- | Memoize an ordered type with a bits instance.
bits :: (Ord a, Bits a) => Memo a
bits f = IntTrie.apply (fmap f IntTrie.identity)

إنها الوظيفة الوحيدة (باستثناء الوظائف التافهة). unit :: Memo ()) والتي يمكن أن تعطيك Memo a قيمة.ويستخدم نفس الفكرة كما في هذا صفحة حول تحفيظ هاسكل.يعرض القسم 2 أبسط استراتيجية للحفظ باستخدام القائمة، ويفعل القسم 3 نفس الشيء باستخدام شجرة ثنائية من المواد الطبيعية المشابهة للشجرة الثنائية. IntTree المستخدمة في memocombinators.

الفكرة الأساسية هي استخدام البناء مثل (map fib [0 ..] !!) أو في حالة memocombinators - IntTrie.apply (fmap f IntTrie.identity).الشيء الذي يجب ملاحظته هنا هو المراسلات بين IntTie.apply و !! وبين أيضا IntTrie.identity و [0..].

الخطوة التالية هي حفظ الوظائف باستخدام أنواع أخرى من الوسائط.ويتم ذلك مع wrap الدالة التي تستخدم التماثل بين الأنواع a و b لبناء أ Memo b من Memo a.على سبيل المثال:

Memo.integral f
=>
wrap fromInteger toInteger bits f
=>
bits (f . fromInteger) . toInteger
=>
IntTrie.apply (fmap (f . fromInteger) IntTrie.identity) . toInteger
~> (semantically equivalent)
(map (f . fromInteger) [0..] !!) . toInteger

يتعامل باقي الكود المصدري مع أنواع مثل القائمة، وربما، وإما وحفظ الوسائط المتعددة.

Answer 3

تم تنفيذ بعض الأعمال بواسطة IntTrie: http://hackage.haskell.org/package/data-inttrie-0.0.4

مكتبة Luke هي نسخة مختلفة من مكتبة Conal's MemoTrie، والتي وصفها هنا: http://conal.net/blog/posts/elegant-memoization-with-functional-memo-tries/

بعض التوسع الإضافي - الفكرة العامة وراء الحفظ الوظيفي هي أخذ وظيفة منها a -> b وتعيينها عبر بنية بيانات مفهرسة بواسطة كله ممكن قيم a وتحتوي على قيم b.يجب أن تكون بنية البيانات هذه كسولة بطريقتين - أولاً يجب أن تكون كسولة في القيم التي تحملها.ثانياً: أن يتم إنتاجه بنفسه بتكاسل.الأول افتراضيًا بلغة غير صارمة.ويتم تحقيق هذا الأخير باستخدام المحاولات المعممة.

تعد الأساليب المختلفة لمركبات المذكرات والمذكرات وما إلى ذلك مجرد طرق لإنشاء تركيبات من أجزاء من المحاولات على أنواع فردية من هياكل البيانات للسماح بالبناء البسيط لمحاولات للهياكل المتزايدة التعقيد.

Answer 4

luqui شيء واحد غير واضح بالنسبة لي: هل هذا له نفس السلوك التشغيلي كما يلي: giveacodicetagpre.

ما سبق يجب أن يحمي FIB على المستوى الأعلى، وبالتالي إذا حددت وظيفتين: giveacodicetagpre.

إذا كنا نحسب f 5 ، فإننا نحصل على fib 5 لا يعود إدخالها عند الحوسبة Fib 6 .ليس من الواضح بالنسبة لي ما إذا كانت مجاكاة الذقذ لها نفس السلوك (أي Memoization المستوى الأعلى بدلا من تحظر إعادة التعويض فقط "داخل" حساب FIB)، وإذا كان الأمر كذلك، فلماذا بالضبط؟