كيف يمكنك إنشاء وظيفة حفظ عامة في هاسكل؟

Question

رأيت آخر حول هذا الموضوع, ولكن هل هناك طريقة نظيفة للقيام بذلك في هاسكل؟

كجزء ثاني، هل يمكن أيضًا القيام بذلك دون جعل الدالة أحادية؟

Answer 1

هذا يتبع إلى حد كبير http://www.haskell.org/haskellwiki/Memoization.

تريد وظيفة من النوع (أ -> ب).إذا لم تسمي نفسها ، فيمكنك فقط كتابة غلاف بسيط يقوم بتخزين قيم الإرجاع.تعتمد أفضل طريقة لتخزين هذا التعيين على خصائص A التي يمكنك استغلالها.الطلب هو الحد الأدنى إلى حد كبير.مع الأعداد الصحيحة ، يمكنك بناء قائمة Lainite Lazy Lazy أو شجرة تحمل القيم.

type Cacher a b = (a -> b) -> a -> b

positive_list_cacher :: Cacher Int b
positive_list_cacher f n = (map f [0..]) !! n

أو

integer_list_cacher :: Cacher Int b
integer_list_cacher f n = (map f (interleave [0..] [-1, -2, ..]) !!
    index n where
        index n | n < 0  = 2*abs(n) - 1
        index n | n >= 0 = 2 * n

لذلك، لنفترض أنه متكرر.ثم تحتاج إلى استدعاء نفسه ، ولكن النسخة المذكرة ، لذلك يمكنك تمرير ذلك بدلاً من ذلك:

f_with_memo :: (a -> b) -> a -> b
f_with_memo memoed base = base_answer
f_with_memo memoed arg  = calc (memoed (simpler arg))

النسخة المحفوظة هي بالطبع ما نحاول تحديده.

لكن يمكننا البدء بإنشاء دالة تقوم بتخزين مدخلاتها مؤقتًا:

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

بفضل الكسل، لا توجد مشكلة:

memoize cacher f = cached where
         cached = cacher (f cached)

فكل ما نحتاج إليه هو استخدامه:

exposed_f = memoize cacher_for_f f

تقدم المقالة تلميحات حول كيفية استخدام فئة النوع التي تختار على الإدخال إلى الوظيفة للقيام بما سبق ، بدلاً من اختيار وظيفة التخزين المؤقت الصريحة.يمكن أن يكون هذا لطيفًا حقًا - بدلاً من بناء ذاكرة التخزين المؤقت بشكل صريح لكل مجموعة من أنواع الإدخال ، يمكننا الجمع ضمنيًا بين ذاكرة التخزين المؤقت للأنواع A و B في ذاكرة التخزين المؤقت لدالة أخذ A و B.

تحذير أخير:إن استخدام هذه التقنية البطيئة يعني أن ذاكرة التخزين المؤقت لا تتقلص أبدًا ، بل تنمو فقط.إذا استخدمت بدلاً من ذلك موناد IO ، فيمكنك إدارة هذا ، ولكن القيام بذلك يعتمد بحكمة على أنماط الاستخدام.

Answer 2

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

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

أي.يمكنه حفظ أي وظيفة من ملف.ثم توفر الوحدة بعض البدائيات (مثل unit :: Memo () و integral :: Memo Int)، ومجموعات لإنشاء جداول مذكرة أكثر تعقيدًا (مثل pair :: Memo a -> Memo b -> Memo (a,b) و list :: Memo a -> Memo [a]).

Answer 3

يمكنك تعديل حل جوناثان باستخدام unsafePerformIO لإنشاء نسخة حفظ "خالصة" لوظيفتك.

import qualified Data.Map as Map
import Data.IORef
import System.IO.Unsafe

memoize :: Ord a => (a -> b) -> (a -> b)
memoize f = unsafePerformIO $ do 
    r <- newIORef Map.empty
    return $ \ x -> unsafePerformIO $ do 
        m <- readIORef r
        case Map.lookup x m of
            Just y  -> return y
            Nothing -> do 
                    let y = f x
                    writeIORef r (Map.insert x y m)
                    return y

سيعمل هذا مع الوظائف العودية:

fib :: Int -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib_memo (n-1) + fib_memo (n-2)

fib_memo :: Int -> Integer
fib_memo = memoize fib

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

f :: String -> [Int] -> Float
f ...

f_memo = curry (memoize (uncurry f))

Answer 4

ومن خلال إجراء ترجمة مباشرة من اللغات الأكثر أهمية، توصلت إلى هذا.

memoize :: Ord a => (a -> IO b) -> IO (a -> IO b)
memoize f =
  do r <- newIORef Map.empty
     return $ \x -> do m <- readIORef r
                       case Map.lookup x m of
                            Just y  -> return y
                            Nothing -> do y <- f x
                                          writeIORef r (Map.insert x y m)
                                          return y

ولكن هذا غير مرض إلى حد ما.أيضًا، خريطة البيانات يقيد المعلمة لتكون مثيلاً لـ أورد.

Answer 5

إذا كانت الحجج الخاصة بك ستكون أعدادًا طبيعية، فيمكنك القيام ببساطة بما يلي:

memo f = let values = map f [0..]
     in \n -> values !! n

ومع ذلك، فإن هذا لا يساعدك حقًا في التغلب على فائض المكدس، ولا يعمل مع الاستدعاءات المتكررة.يمكنك رؤية بعض الحلول الرائعة على http://www.haskell.org/haskellwiki/Memoization.