Come iterativo può approfondire la ricerca implementata efficace in Haskell?

Question

Ho un problema di ottimizzazione che voglio risolvere. Hai qualche tipo di struttura di dati:

data Foo =
  { fooA :: Int
  , fooB :: Int
  , fooC :: Int
  , fooD :: Int
  , fooE :: Int
}

e una funzione Valutazione:

rateFoo :: myFoo -> Int

devo ottimizzare il risultato di rateFoo modificando i valori nella struct. In questo caso specifico, ho deciso di utilizzare iterativo di ricerca approfondendo per risolvere il problema. L'(infinito) albero di ricerca per la migliore ottimizzazione è stato creato da un'altra funzione, che si applica semplicemente tutti i possibili cambiamenti recursivly all'albero:

fooTree :: Foo -> Tree

La mia ricerca sguardi funzione simile a questa:

optimize :: Int -> Foo -> Foo
optimize threshold foo = undefined

La domanda che avevo, prima di iniziare è questo:

  

Come l'albero può essere generata dai dati in ogni punto, è possibile avere solo le parti dell'albero generato, che sono attualmente necessari dall'algoritmo? E 'possibile avere la memoria liberata e l'albero rigenerata, se necessario, al fine di risparmiare memoria (A congedo a livello n possono essere generati in O(n) e n rimane piccola, ma non abbastanza piccolo per avere tutto l'albero in memoria nel tempo)?

     

E 'questo qualcosa che posso excpect dal runtime? Può il runtime unevaluate (espressioni trasformare un'espressione valutata in un uno non valutata)? O che cosa è la sporca incidere devo fare per questo?

Answer 1

Ecco il mio consiglio:

1. Basta implementare l'algoritmo in la maggior parte modo diretto possibile.
2. Profilo.
3. Ottimizza per l'utilizzo di velocità o la memoria, se necessario.

I molto rapidamente imparato che io non sono intelligente e / o abbastanza esperienza per ragionare su ciò che GHC farà o come garbage collection funzionerà. A volte le cose che sono sicuro saranno disastrosamente inefficiente memoria di lavoro senza intoppi la prima volta intorno, e meno spesso le cose che sembrano semplici richiedono un sacco di armeggiare con annotazioni rigore, ecc.

Real World Haskell profilazione e ottimizzazione è incredibilmente utile una volta che si arriva a passaggi 2 e 3.

---

Per esempio, ecco una semplice implementazione di IDDFS, dove f espande i bambini, p è il predicato di ricerca, e x è il punto di partenza.

search :: (a -> [a]) -> (a -> Bool) -> a -> Bool
search f p x = any (\d -> searchTo f p d x) [1..]
  where
    searchTo f p d x
      | d == 0    = False
      | p x       = True
      | otherwise = any (searchTo f p $ d - 1) (f x)

ho provato effettuando una ricerca per "abbaaaaaacccaaaaabbaaccc" con children x = [x ++ "a", x ++ "bb", x ++ "ccc"] come f. Sembra ragionevolmente veloce e richiede pochissima memoria (lineare con la profondità, credo). Perché non provare qualcosa di simile prima e poi passare ad una struttura dati più complicata se non è abbastanza buono?

Answer 2

Il tempo di esecuzione non espressioni non unevaluate.

C'è un modo semplice per ottenere quello che vuoi però.

Si consideri una cerniera-come la struttura per il vostro albero. Ogni nodo contiene un valore e un thunk rappresenta giù, su, ecc Quando si sposta al nodo successivo, è possibile spostare normalmente (ponendo il valore del nodo precedente nella fessura corrispondente) o forgetfully (immissione un'espressione che alla precedente nodo nello slot di destra). Poi si ha il controllo su quanto "storia" si riaggancia a.