Programmazione funzionale e algoritmi stateful

12

Sto imparando la programmazione funzionale con Haskell . Nel frattempo sto studiando la teoria degli automi e siccome i due sembrano adattarsi bene, sto scrivendo una piccola libreria per giocare con gli automi.

Ecco il problema che mi ha fatto porre la domanda. Mentre studiavo un modo per valutare la raggiungibilità di uno stato, ho avuto l'idea che un semplice algoritmo ricorsivo sarebbe abbastanza inefficiente, perché alcuni percorsi potrebbero condividere alcuni stati e potrei finire per valutarli più di una volta.

Ad esempio, qui, valutando raggiungibilità di g da a , dovrei escludere f entrambi mentre controllano il percorso attraverso d e c :

Quindilamiaideaècheunalgoritmochelavorainparallelosumoltipercorsiecheaggiorniunrecordcondivisodistatiesclusipotrebbeesseregrandioso,maètroppoperme.

Hovistocheinalcunisemplicicasidiricorsionesipuòpassareallostatocomeargomento,edèquellochedevofarequi,perchépassoavantilalistadeglistatichehopassatoperevitareiloop.Mac'èunmodoperpassareanchequellalistaall'indietro,comerestituirlainunatuplainsiemealrisultatobooleanodellamiafunzionecanReach?(anchesequestosembraunpo'forzato)

Oltreallavaliditàdelmiocasodiesempio,qualialtretecnichesonodisponibiliperrisolverequestotipodiproblemi?Credochequestidebbanoessereabbastanzacomunidadoveresseresoluzionicomequellochesuccedeconfold*omap.

Finora,leggendo learnyouahaskell.com non ne ho trovato nessuno, ma considera che non ho ancora toccato le monadi.

( se interessato, ho pubblicato il mio codice su codereview )

    
posta bigstones 05.10.2013 - 00:29
fonte

2 risposte

16

La programmazione funzionale non elimina lo stato. Lo rende solo esplicito! Mentre è vero che funzioni come la mappa spesso "districano" una struttura dati "condivisa", se tutto ciò che vuoi è scrivere un algoritmo di raggiungibilità, allora è solo questione di tenere traccia di quali nodi hai già visitato:

import qualified Data.Set as S
data Node = Node Int [Node] deriving (Show)

-- Receives a root node, returns a list of the node keyss visited in a depth-first search
dfs :: Node -> [Int]
dfs x = fst (dfs' (x, S.empty))

-- This worker function keeps track of a set of already-visited nodes to ignore.
dfs' :: (Node, S.Set Int) -> ([Int], S.Set Int)
dfs' ([email protected](Node k ns), s )
  | k  'S.member' s = ([], s)
  | otherwise =
    let (childtrees, s') = loopChildren ns (S.insert k s) in
    (k:(concat childtrees), s')

--This function could probably be implemented as just a fold but Im lazy today...
loopChildren :: [Node] -> S.Set Int -> ([[Int]], S.Set Int)
loopChildren []  s = ([], s)
loopChildren (n:ns) s =
  let (xs, s') = dfs' (n, s) in
  let (xss, s'') = loopChildren ns s' in
  (xs:xss, s'')

na = Node 1 [nb, nc, nd]
nb = Node 2 [ne]
nc = Node 3 [ne, nf]
nd = Node 4 [nf]
ne = Node 5 [ng]
nf = Node 6 []
ng = Node 7 []

main = print $ dfs na -- [1,2,5,7,3,6,4]

Ora, devo confessare che tenere traccia di tutto questo stato a mano è piuttosto fastidioso e soggetto a errori (è facile usare s 'invece di s' ', è facile passare lo stesso s' a più di un calcolo. ..). È qui che entrano le monadi: non aggiungono nulla che non potevi già fare prima, ma ti permettono di passare la variabile di stato attorno implicitamente e l'interfaccia garantisce che ciò avvenga in un modo a thread singolo.

Modifica: cercherò di dare un ulteriore ragionamento su ciò che ho fatto ora: prima di tutto, invece di testare solo la raggiungibilità, ho codificato una ricerca in profondità. L'implementazione sembrerà più o meno la stessa, ma il debug sembra un po 'meglio.

In un linguaggio di stato, il DFS sarebbe un po 'come questo:

visited = set()  #mutable state
visitlist = []   #mutable state
def dfs(node):
   if isMember(node, visited):
       //do nothing
   else:
       visited[node.key] = true           
       visitlist.append(node.key)
       for child in node.children:
         dfs(child)

Ora dobbiamo trovare un modo per sbarazzarci dello stato mutabile. Prima di tutto ci liberiamo della variabile "visitlist" facendo sì che dfs restituisca quello invece di void:

visited = set()  #mutable state
def dfs(node):
   if isMember(node, visited):
       return []
   else:
       visited[node.key] = true
       return [node.key] + concat(map(dfs, node.children))

E ora arriva la parte difficile: sbarazzarsi della variabile "visitata". Il trucco di base è usare una convenzione in cui passiamo lo stato come parametro aggiuntivo alle funzioni che ne hanno bisogno e le funzioni restituiscono la nuova versione dello stato come valore di ritorno aggiuntivo se vogliono modificarlo.

let increment_state s = s+1 in
let extract_state s = (s, 0) in

let s0 = 0 in
let s1 = increment_state s0 in
let s2 = increment_state s1 in
let (x, s3) = extract_state s2 in
-- and so on...

Per applicare questo modello al dfs, dobbiamo cambiarlo per ricevere il set "visitato" come parametro aggiuntivo e per restituire la versione aggiornata di "visitato" come un valore di ritorno extra. Inoltre, dobbiamo riscrivere il codice in modo da passare sempre in avanti la versione "più recente" dell'array "visited":

def dfs(node, visited1):
   if isMember(node, visited1):
       return ([], visited1) #return the old state because we dont want to  change it
   else:
       curr_visited = insert(node.key, visited1) #immutable update, with a new variable for the new value
       childtrees = []
       for child in node.children:
          (ct, curr_visited) = dfs(child, curr_visited)
          child_trees.append(ct)
       return ([node.key] + concat(childTrees), curr_visited)

La versione di Haskell fa più o meno quello che ho fatto qui, tranne che va fino in fondo e usa una funzione ricorsiva interna invece delle mutabili variabili "curr_visited" e "childtrees".

Per quanto riguarda le monadi, ciò che in pratica realizzano è far passare implicitamente il "curr_visited", invece di costringerti a farlo a mano. Non solo rimuove il disordine dal codice, ma impedisce anche di commettere errori, come lo stato di biforcazione (passando lo stesso set "visitato" a due chiamate successive anziché concatenare lo stato).

    
risposta data 05.10.2013 - 17:03
fonte
2

Ecco una risposta semplice basata su mapConcat .

 mapConcat :: (a -> [b]) -> [a] -> [b]
 -- mapConcat is in the std libs, mapConcat = concat . map
 type Path = []

 isReachable :: a -> Auto a -> a -> [Path a]
 isReachable to auto from | to == from = [[]]
 isReachable to auto from | otherwise = 
    map (from:) . mapConcat (isReachable to auto) $ neighbors auto from

Dove neighbors restituisce gli stati immediatamente connessi a uno stato. Questo restituisce una serie di percorsi.

    
risposta data 05.10.2013 - 04:17
fonte

Leggi altre domande sui tag