Come si può scrivere funzionalmente l'algoritmo iterativo su una raccolta modificata dinamicamente con condizioni dipendenti?

Question

Ho l'algoritmo che elimina nodi irraggiungibili grafo iniziano nodo specificato e secondo lista di input dei marchi bordo:

let g = Set.ofList [ (0, false, 1); 
        (0, true, 2); 
        (1, true, 3); 
        (1, false, 4); 
        (2, true, 4); 
        (4, false, 4); ] 

let nextNode graph prev value = graph |> Seq.tryPick (function 
    | prev', value', next when prev = prev' && value = value' -> Some next 
    | _ -> None) 

let noIncoming graph node = 
      not <| Set.exists (fun (_, _, node') -> node = node') graph 

let clearEdges graph start input = 
    let graph' = ref graph 
    let current = ref (Some start) 
    input 
    |> Seq.takeWhile (fun _ -> Option.exists (noIncoming !graph') !current) 
    |> Seq.iter (fun value -> 
      let next = nextNode !graph' (!current).Value value 
      graph' := Set.filter (fun (current', _, _) -> (!current).Value <> current') !graph' 
      current := next) 
    graph' 

clearEdges g 0 [false; true] 

> val it : Set<int * bool * int> ref = 
    {contents = set [(2, true, 4); (4, false, 4)];} 

Funziona, ma sospetto che il mio algoritmo clearEdges con riferimenti è brutto e non è F # -styled, per quanto ho capito. Ho provato a scriverlo funzionalmente, ma probabilmente ho ricevuto il mix di algoritmo iterativo e metodi di raccolta. C'è qualche approccio funzionale per farlo? Perché considero che il brutto codice di lavoro sia peggio di nessun codice. Grazie.

Answer 1

Come altri hanno detto nelle risposte e nei commenti, la parte più difficile nel rispondere a questo è la comprensione del codice. Manca una buona descrizione e commenti.

La prima cosa che ho fatto per capire il codice è stato aggiungere le firme di tipo e quindi le istruzioni printfn al codice per vedere cosa stava facendo.

Dopo ciò è molto più facile capire il codice nella domanda.

In riprogettazione del codice non ho provato a modificare piccole parti alla volta, ma ho iniziato da zero a sviluppare le funzioni principali in base a ciò che ho appreso dall'output printfn e alle firme dei tipi. Senza esitazione sono passato dal codice mutabile usando ref a un grafico immutabile che è stato ricostruito da zero in ogni funzione.Potrebbe sembrare uno spreco buttare fuori una struttura dati esistente e costruirne una nuova ogni volta, ma pensaci in questo modo: le funzioni che devono prendere una decisione su ogni spigolo devono visitare ogni spigolo così quando visiti ogni spigolo o lo aggiungi al nuovo grafico o no, ciò rende la codifica molto più semplice e anche molto più semplice per gli altri che cercano di capirlo.

Ho anche aggiunto i tipi per rendere più significative le firme dei tipi e per aggiungere chiarezza a ciò che il codice sta facendo. Grande bonus per un po 'di lavoro.

Ho quindi esaminato le funzioni e invece di concentrarmi sul rendere il codice il più conciso possibile incentrato sulla leggibilità e sulla manutenibilità e ha preso in considerazione una funzione per renderla più pronunciata.

Chiaramente questa risposta è più lunga delle altre due, ma è più funzionale del codice originale, non è mutabile, è più facile da capire alla prima lettura e commentata per spiegare cosa fa ciascuna funzione.

Se questo dovesse far parte di una libreria, il codice dovrebbe essere modificato per rimuovere le firme del tipo e se questo dovesse essere generico non sarebbe un'opzione. Inoltre, crea le funzioni interne delle funzioni separate e riduci alcune parti per utilizzare le funzioni di base F # integrate e aggiungi altri commenti per compensare la perdita di chiarezza quando lo fai.

In una versione precedente ho usato List.pick ma resi conto che potrebbe gettare un'eccezione KeyNotFoundException e dal momento che mi piacciono le mie funzioni da total quando possibile modificato per evitare l'eccezione.

Nel guardare la mia risposta non ero contento di if not (nodeUsed graph node) then; era una verruca nel mezzo della semplicità. Così ho deciso di ricorrere al vecchio coltellino svizzero di programmazione funzionale: factoring. La programmazione Pure functional è fondamentalmente espressioni che possono essere considerate come espressioni matematiche o, più in teoria, term rewriting. Sapevo che se avessi potuto calcolare la linea con lo not, avrei potuto renderlo più bello e più facile da comprendere. Quindi il modo per calcolare il not era spostarlo all'esterno dello let rec, ad es. pathToNodes e ciò potrebbe essere eseguito passando un elenco di nodi anziché un elenco di transizioni, ad es. reduceGraph2. Fatto ciò, il codice raggiunse la semplicità.

Sono sicuro che si può ridurre ulteriormente il codice, ma in genere lascia le mie risposte come questa per le nuove persone F # perché sono più facili da comprendere.

namespace Workspace 

module main = 

    type Node = int 
    type Transition = bool 
    type Edge = Node * Transition * Node 
    type Path = Transition list 
    type Graph = Edge list 

    [<EntryPoint>] 
    let main argv = 

     let edge1 : Edge = (0, false, 1) 
     let edge2 : Edge = (0, true , 2) 
     let edge3 : Edge = (1, true , 3) 
     let edge4 : Edge = (1, false, 4) 
     let edge5 : Edge = (2, true , 4) 
     let edge6 : Edge = (4, false, 4) 

     let g : Graph = [edge1; edge2; edge3; edge4; edge5; edge6] 

     // Given a Node, are there any Edges to that node 
     let nodeUsed (graph : Graph) (checkNode : Node) : bool = 
      List.exists (fun (_, _, toNode) -> checkNode = toNode) graph 

     // Given a Node and a transition, what is the next node 
     // This assumes that Transition is binary 
     // so only a value will be returned instead of a list. 
     let nextNode (graph : Graph) (fromNode : Node) (transition : Transition) : Node option = 
      let rec pick (graph : Graph) (fromNode : Node) (transition : Transition) : Node option = 
       match graph with 
       | (f, c, t)::tl when (f = fromNode) && (c = transition) -> Some t 
       | hd::tl -> pick tl fromNode transition 
       | _ -> None 
      pick graph fromNode transition 

     // Given a graph and a node, remove all edges that start from that node. 
     // This builds a new graph each time, thus the graph is immutable. 
     let removeNode (graph : Graph) (node : Node) : Graph = 
      let rec removeEdges graph node newGraph = 
       match graph with 
       | hd::tl -> 
        let (f,c,t) = hd 
        if (f = node) 
        // Don't add current node to new graph 
        then removeEdges tl node newGraph 
        // Add current node to new graph 
        else removeEdges tl node ((f,c,t) :: newGraph) 
       | [] -> newGraph 
      removeEdges graph node [] 

     // or 

     // let removeNode (graph : Graph) (node : Node) : Graph = 
     //  let choiceFunction elem = 
     //   match elem with 
     //   | (f,c,t) when f = node -> None 
     //   | _ -> Some(elem) 
     //  List.choose choiceFunction graph 

     // Given a graph, a starting node, and a list of transitions (path), 
     // return a new reduced graph based on the example code in the SO question. 
     let reduceGraph (graph : Graph) (start : Node) (path : Path) : Graph = 
      let rec processTransistion graph node transitions = 
       if not (nodeUsed graph node) then 
        match transitions with 
        | (transistion :: transitions) -> 
         // Get next node before removing nodes used to get next node 
         let nextNodeResult = nextNode graph node transistion 
         match nextNodeResult with 
         | Some(nextNode) -> 
          let newGraph = removeNode graph node 
          processTransistion newGraph nextNode transitions 
         | None -> graph 
        | [] -> graph 
       else graph 
      processTransistion graph start path 

     let result = reduceGraph g 0 [false; true] 
     printfn "reduceGraph - result: %A" result 

     printf "Press any key to exit: " 
     System.Console.ReadKey() |> ignore 
     printfn "" 

     0 // return an integer exit code 

.

// Give an graph, a node and a path, 
    // convert the transition list (path) to a node list 
    let pathToNodes (graph : Graph) (start : Node) (path : Path) : (Node List) = 
     let rec visit graph node transistions acc = 
      match transistions with 
      | (transition::rest) -> 
       match (nextNode graph node transition) with 
       | Some(nextNode) -> visit graph nextNode rest (nextNode :: acc) 
       | None -> List.rev acc 
      | [] -> List.rev acc 
     visit graph start path [start] 

    // Given a graph, a starting node, and a list of transitions (path), 
    // return a new reduced graph based on the example code in the SO question. 
    // This variation does so internally by a node list instead of a transition list 
    let reduceGraph2 (graph : Graph) (start : Node) (path : Path) : Graph = 
     let rec processNodes graph nodes = 
      match nodes with 
      | (currentNode :: rest) -> processNodes (removeNode graph currentNode) rest 
      | [] -> graph 
     let nodes = pathToNodes graph start path 
     processNodes graph nodes 

Answer 2

Come suggerito da altri, probabilmente si desidera rimuovere la riassegnazione tramite l'uso di una cella di riferimento e invece si accumula uno stato utilizzando una piega o una ricorsione. Ecco cosa mi è venuto in mente:

let reachedNodes graph start fullPath = 
    let rec loop path acc node = 
     match path with 
     | [] -> node :: acc 
     | v :: rest -> 
      let next = 
       graph 
       |> Seq.tryPick (fun (prev, value, next) -> 
        if prev = node && value = v then Some next 
        else None) 
      match next with 
      | Some c -> loop rest (node :: acc) c 
      | None -> node :: acc 
    loop fullPath [] start 
    |> Set.ofList 

let clearEdges graph start path = 
    let reachedNodes' = reachedNodes graph start path 
    let notInReachedNodes n = Set.contains n reachedNodes' |> not 
    graph 
    |> Set.filter (fun (prev, _, next) -> notInReachedNodes prev && notInReachedNodes next) 

Hai usato un set di spigoli per rappresentare il tuo grafico. Ciò impedisce un bordo completamente duplicato, ma consente comunque di dichiarare stati illegali: ad es. 0 potrebbe avere due bordi true in uscita su nodi diversi. Potrebbe essere meglio rappresentare il tuo grafico come una mappa di (node, value) a node. Questo potrebbe anche migliorare le prestazioni di questo caso perché trarrai vantaggio dalla ricerca della chiave della mappa.

Answer 3

Si prega di documentare nel codice risultante cosa sta facendo questa funzione e perché! Mi ci è voluto un po 'per capire cosa sta succedendo, perché non mi aspettavo che clearEdges passasse sopra un elenco fisso di hop con due condizioni di interruzione durante l'eliminazione dei bordi in uscita.

Si potrebbe cambiare la struttura dei dati a questo, che aggiunge un certo tipo di sicurezza e rende attraversando il grafico più semplice:

type Node = Node of int 

let g = Map.ofList [ (Node 0, false), Node 1 
        (Node 0, true), Node 2 
        (Node 1, true), Node 3 
        (Node 1, false), Node 4 
        (Node 2, true), Node 4 
        (Node 4, false), Node 4 ] 

Poi, clearEdges può essere scritta in questo modo:

let rec clearEdges graph node hopList = 
    if List.isEmpty hopList || Map.exists (fun _ dst -> dst = node) graph then graph 
    else let graph' = Map.filter (fun (src, _) _ -> src <> node) graph 
     match Map.tryFind (node, hopList.Head) graph with 
     | None -> graph' 
     | Some node -> clearEdges graph' node hopList.Tail 

senza ulteriori funzioni richieste. La chiamata cambia in clearEdges g (Node 0) [false; true].