Wie stellen Sie eine generische memoize Funktion in Haskell?
-
02-07-2019 - |
Frage
Ich habe gesehen, href="https://stackoverflow.com/questions/129877/how-do-i-write-a-generic-memoize-function"> , aber ist es eine saubere Möglichkeit, dies in Haskell zu tun?
Als zweiten Teil kann es auch ohne dass die Funktion monadischen getan werden?
Lösung
Dieses weitgehend folgt http://www.haskell.org/haskellwiki/Memoization .
Sie möchten eine Funktion vom Typ (a -> b). Wenn sie sich nicht nennen, dann Sie können nur eine einfache Wrapper schreiben, die die Rückgabewerte zwischenspeichert. Das beste Weg, um diese Zuordnung zu speichern, hängt davon ab, welche Eigenschaften einer Dose Sie Ausbeuten. Bestellen ist so ziemlich ein Minimum. mit ganzen Zahlen Sie können eine unendliche faul Liste erstellen oder zu Baum, um die Werte zu halten.
type Cacher a b = (a -> b) -> a -> b
positive_list_cacher :: Cacher Int b
positive_list_cacher f n = (map f [0..]) !! n
oder
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
Also, nehme an, es rekursiv ist. Dann brauchen Sie es nicht selbst zu nennen, aber die memoized Version, so dass Sie passieren, dass in statt:
f_with_memo :: (a -> b) -> a -> b
f_with_memo memoed base = base_answer
f_with_memo memoed arg = calc (memoed (simpler arg))
Die memoized Version ist natürlich, was wir zu definieren versuchen.
Aber wir können durch die Schaffung einer Funktion starten, die ihre Eingänge Caches:
Wir können eine Ebene konstruieren in einer Funktion, indem die eine schafft Struktur, die Werte zwischenspeichert. Außer wir brauchen die Version von f erstellen dass bereits die im Cache-Funktion übergeben.
Durch Faulheit, ist das kein Problem:
memoize cacher f = cached where
cached = cacher (f cached)
dann alles, was wir brauchen, ist, es zu benutzen:
exposed_f = memoize cacher_for_f f
Der Artikel gibt Hinweise, wie eine Typklasse Auswahl auf dem verwenden Eingabe in die Funktion des oben, anstatt die Wahl eines expliziten zu tun Caching-Funktion. Das kann wirklich schön sein - und nicht explizit einen Cache für jede Kombination von Eingangstypen konstruieren, können wir implizit kombinieren Caches für Typen a und b in einen Cache für eine Funktion a und b nehmen.
Ein letzter Hinweis: Um diese faul Technik bedeutet, dass der Cache nie schrumpft, es wächst nur. Wenn Sie stattdessen die IO Monade verwenden, können Sie diese verwalten, aber tut es hängt mit Bedacht auf Nutzungsmuster.
Andere Tipps
Die Paketdaten-memocombinators auf Hackage bietet viele wiederverwendbare memoization Routinen. Die Grundidee ist:
type Memo a = forall r. (a -> r) -> (a -> r)
d. es kann eine beliebige Funktion von einem memoize. Das Modul liefert dann einige Grundelemente (wie unit :: Memo ()
und integral :: Memo Int
) und Kombinatoren für den Aufbau komplexer Memo-Tabellen (wie pair :: Memo a -> Memo b -> Memo (a,b)
und list :: Memo a -> Memo [a]
).
Sie können Jonathan's Lösung mit unsafePerformIO ändern, um eine „reine“ memoizing Version Ihrer Funktion zu erstellen.
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
Dies wird mit rekursiven Funktionen arbeiten:
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
Altough dieses Beispiel eine Funktion mit einem Integer-Parameter ist, sagt die Art der memoize uns, dass es mit einer beliebigen Funktion verwendet werden kann, die eine vergleichbare Art nimmt. Wenn Sie eine Funktion mit mehr als einem Parameter nur gruppieren sie in einem Tupel vor memoize Anwendung. F.i:.
f :: String -> [Int] -> Float
f ...
f_memo = curry (memoize (uncurry f))
eine direkte Übersetzung aus den mehr imperativen Sprachen tun, kam ich mit diesem nach oben.
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
Das ist aber irgendwie unbefriedigend. Auch Data.Map Constraints der Parameter eine Instanz von Ord .
Wenn Sie Ihre Argumente natürliche Zahlen sein werden, können Sie einfach:
memo f = let values = map f [0..]
in \n -> values !! n
Sie jedoch, dass Ihnen wirklich nicht hilft mit dem Stapel überfüllt, und es funktioniert nicht mit rekursiven Aufrufen zu arbeiten. Sie können einige ausgefallenere Lösungen unter http://www.haskell.org/haskellwiki/Memoization .