Memoizzazione delle funzioni haskell interdipendenti

Question

Memoizzazione delle funzioni haskell interdipendenti

#1 da (2 voti)

1

Ho tre funzioni che agiscono su una matrice e il tipo di trovare un percorso di somma minimo (Nota dim = 80, vedi link ):

-- f is the minimum cost from x, y by taking only up and right (up and down doesn't make sense)
f :: [[Int]] -> Int -> Int -> Int
f arr x y
    | y == dim-1 = arr !! x !! y
    | otherwise = arr !! x !! y + if x > 0 then min (h arr x (y+1)) (f arr (x-1) y) else h arr x (y+1)

-- g is the minimum cost from x, y by taking only down and right (up and down doesn't make sense)
g :: [[Int]] -> Int -> Int -> Int
g arr x y
    | y == dim-1 = arr !! x !! y
    | otherwise = arr !! x !! y + if x + 1 < dim then min (h arr x (y+1)) (g arr (x+1) y) else h arr x (y+1)

-- h is the minimum cost from x, y by taking both up, down and right
h :: [[Int]] -> Int -> Int -> Int
h arr x y
    | y == dim-1 = arr !! x !! y
    | otherwise = min (g arr x y) (f arr x y)

Ho provato a usare Data.Function.Memoize ma anche questo non funzionava (credo fermamente che stia facendo qualcosa di sbagliato), cioè stavo facendo memoF = memoize f e così via e sostituendo le chiamate a f , g e h con memoF e così via.

Ho finalmente bisogno di trovare minimum [h arr x 0 | x <- [0..dim-1]] .

Cosa dovrei fare?

haskell

posta RE60K 02.06.2017 - 14:33

fonte

1 risposta

Leggi altre domande sui tag haskell

Quale modello per l'implementazione di più interfacce sullo stesso tipo? Migliorare la progettazione delle transizioni di stato in un'applicazione aziendale: il caso dell'annullamento

score 2 · Answer 1

Citando la documentazione del pacchetto di memoizzazione che stai utilizzando:

Note that most memoization in this style relies on assumptions about the implementation of non-strictness (as laziness) that are not guaranteed by the semantics.

Questa libreria si basa su un trucco che dipende dal modo preciso in cui il compilatore Haskell tiene traccia dei termini che sono stati valutati e che non hanno lo scopo di ingannare il compilatore in modo efficace per memorizzare la funzione per te. Come molti hack di implementazione del linguaggio, non è affidabile.

L'idea alla base di tutti questi hack è fingere di avere una tabella competitiva di tutti i possibili risultati e lasciare che la valutazione lazy espanda solo le parti necessarie. Ma la valutazione lenta non ha lo scopo di funzionare in questo modo, e non vi è alcuna garanzia che non si riesca a rivalutare le parti più volte. Se funziona, è fantastico. Ma quando non lo fa:

Il

link implementa la memoizzazione utilizzando un hashtable mutabile. Usa unsafePerformIO per eseguire la mutazione, ma va bene perché è dimostrabile che l'integrità referenziale non è influenzata. Questo è molto più affidabile e ho il sospetto più efficiente rispetto alle altre tecniche.