Come implementare grafici e algoritmi di grafi in un linguaggio di programmazione funzionale?

Question

Fondamentalmente, so come creare strutture di dati del grafico e utilizzare l'algoritmo di Dijkstra nei linguaggi di programmazione in cui sono consentiti effetti collaterali. In genere, gli algoritmi del grafico utilizzano una struttura per contrassegnare determinati nodi come "visitati", ma questo ha effetti collaterali, che sto cercando di evitare.

Posso pensare a un modo per implementarlo in un linguaggio funzionale, ma fondamentalmente richiede il passaggio di grandi quantità di stato a diverse funzioni e mi chiedo se esiste una soluzione più efficiente in termini di spazio.

Answer 1

Si potrebbe verificare come Haskell di Martin Erwig functional graph library fa cose. Ad esempio, i suoi shortest-path functions sono tutti puri e puoi vedere lo source code per come è implementato.

Un'altra opzione, like fmark mentioned, consiste nell'utilizzare un'astrazione che consente di implementare le funzioni pure in termini di stato. Menziona la monade di Stato (che è disponibile in entrambe le varietà lazy e strict). Un'altra opzione, se si sta lavorando nel compilatore/interprete GHC Haskell (o, penso, qualsiasi implementazione Haskell che supporti i tipi rank-2), un'altra opzione è the ST monad, che consente di scrivere funzioni pure che trattano internamente variabili mutabili .

Answer 2

La maggior parte dei linguaggi funzionali supporta le funzioni interne. Quindi puoi semplicemente creare la rappresentazione grafica nello strato più esterno e fare semplicemente riferimento alla funzione interna.

Questo libro copre ampiamente http://www.amazon.com/gp/product/0262510871/ref=pd_lpo_k2_dp_sr_1?ie=UTF8&cloe_id=aa7c71b1-f0f7-4fca-8003-525e801b8d46&attrMsgId=LPWidget-A1&pf_rd_p=486539851&pf_rd_s=lpo-top-stripe-1&pf_rd_t=201&pf_rd_i=0262011530&pf_rd_m=ATVPDKIKX0DER&pf_rd_r=114DJE8K5BG75B86E1QS

Answer 3

mi piacerebbe sentir parlare di una tecnica molto intelligente, ma penso che ci sono due approcci fondamentali:

1. modificare qualche oggetto stato globale. ovvero gli effetti collaterali
2. Passa il grafico come argomento alle tue funzioni con il valore restituito come grafico modificato. Presumo che questo sia il tuo approccio di "passaggio di grandi quantità di stato"

Questo è ciò che viene fatto nella programmazione funzionale. Se il compilatore/interprete è buono, ti aiuterà a gestire la memoria per te. In particolare, dovrai assicurarti di ricorrere alla ricorsione in coda, se ti capita di ricorrere in una delle tue funzioni.

Answer 4

Se si utilizza haskell, l'unico linguaggio funzionale con cui sono familiare, si consiglia di utilizzare State monad. La monade di stato è un'astrazione per una funzione che accetta uno stato e restituisce un valore intermedio e un nuovo valore di stato. Questo è considered idiomatic haskell per quelle situazioni in cui è necessario mantenere uno stato ampio.

È un'alternativa molto più bella allo "stato restituito come risultato di una funzione e passa come un parametro" idioma che viene enfatizzato nelle esercitazioni di programmazione funzionale per principianti. Immagino che la maggior parte dei linguaggi di programmazione funzionale abbia un costrutto simile.

Answer 5

Ho solo mantenuto il set visitato come un set e lo passo come parametro. Esistono implementazioni efficienti in tempo di registrazione di insiemi di qualsiasi tipo ordinato e insiemi di numeri interi estremamente efficienti.

Per rappresentare un grafico, utilizzo elenchi di adiacenza, o userò una mappa finita che mappa ciascun nodo in un elenco dei suoi successori. Dipende da cosa voglio fare.

Piuttosto che Abelson e Sussman, consiglio a Chris Okasaki di Purely Functional Data Structures. Mi sono collegato alla tesi di Chris, ma se hai i soldi, li ha espansi in un excellent book.

---

Solo per sorrisi, ecco una inversione postorder di ricerca un po 'paura in profondità fatto in stile continuazione-passing in Haskell. Questo è direttamente fuori dalla biblioteca Hoopl ottimizzatore:

postorder_dfs_from_except :: forall block e . (NonLocal block, LabelsPtr e) 
          => LabelMap (block C C) -> e -> LabelSet -> [block C C] 
postorder_dfs_from_except blocks b visited = 
vchildren (get_children b) (\acc _visited -> acc) [] visited 
where 
    vnode :: block C C -> ([block C C] -> LabelSet -> a) 
         -> ([block C C] -> LabelSet -> a) 
    vnode block cont acc visited = 
     if setMember id visited then 
      cont acc visited 
     else 
      let cont' acc visited = cont (block:acc) visited in 
      vchildren (get_children block) cont' acc (setInsert id  visited) 
     where id = entryLabel block 
    vchildren bs cont acc visited = next bs acc visited 
     where next children acc visited = 
       case children of []  -> cont acc visited 
           (b:bs) -> vnode b (next bs) acc  visited 
    get_children block = foldr add_id [] $ targetLabels bloc 
    add_id id rst = case lookupFact id blocks of 
         Just b -> b : rst 
         Nothing -> rst 

Answer 6

Ecco un esempio di Swift. Potresti trovarlo un po 'più leggibile. Le variabili sono in realtà un nome descrittivo, a differenza degli esempi Haskell super criptici.

https://github.com/gistya/Functional-Swift-Graph