How can iterative algorithm over a dynamically changed collection with depended condition be written functionally?

Question

I have the algorithm that deletes unreachable nodes of graph starting with specified node and according to input list of edge marks:

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)];}

It works, but I suspect that my algorithm clearEdges with references is ugly and is not F#-styled, as far as I understand. I have tried to write it functionally, but probably I've received the mix of iterative algorithm and collection methods. Is there any functional approach to do that? Because I consider that ugly working code is worse than no code. Thanks.

Answer 1

As others have said in the answers and comments, the hardest part about answering this is understanding the code. It lacks a good description and comments.

The first thing I did to understand the code was to add the type signatures and then printfn statements to your code to see what it was doing.

After that it because much easier to understand the code in the question.

In redesigning the code I did not try to change small parts at a time but started from scratch building up the core functions based on what I learned from the printfn output and type signatures. Without hesitation I switched from the mutable code using ref to an immutable graph that was rebuilt from scratch in each function. That may seem like a waste to throw out an existing data structure and construct a new one each time, but think about it this way: the functions that have to make a decision on each edge have to visit each edge so when you visit each edge you either add it to the new graph or don't, that makes coding it much easier and also much easier for others trying to understand it.

I also added the types to make the type signatures more meaningful and to add clarity to what the code is doing. Big bonus for a little bit of work.

I then looked at the functions and instead of focusing on making the code as concise as possible focused on readability and maintainability, and factored a function to make it more pronounced.

Clearly this answer is longer than the other two, but is more functional than the original code, no mutables, easier to understand on the first read, and commented to explain what each function does.

If this were to be part of a library the code should be modified to remove the type signatures and if this were to be generic that would not be an option. Also make the separate functions inner functions and refactor some of it down to make use of built-in F# core functions and add more comments to compensate for the loss of clarity when doing so.

In an earlier version I used List.pick but realized it could throw a KeyNotFoundException exception and since I like my functions to be total when possible modified it to avoid the exception.

In looking at my answer I was not happy with if not (nodeUsed graph node) then; it was a wart in the middle of simplicity. So I decided to resort to the old Swiss army knife of functional programming: factoring. Pure functional programming is basically expressions that can be factored like math expressions, or more theoretically term rewriting. I knew if I could factor out the line with the not I could make it more beautiful and this easier to comprehend. So the way to factor out the not was to move it outside of the let rec, e.g. pathToNodes, and that could be done by passing in a list of nodes instead of a list of transitions, e.g. reduceGraph2. Once that was done the code reached simplicity.

I am sure one can factor the code down more but I typically leave my answers like this for the new F# people because they are easier to comprehend.

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

Please document in your resulting code what this function is doing and why! It took me a while to figure out what is going on, as I didn't expect clearEdges to go over a fixed list of hops with two abort conditions while deleting outgoing edges.

You could change the data structure to this, which adds some type safety and makes traversing the graph easier:

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 ]

Then, clearEdges can be written like this:

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

with no further functions required. The call changes to clearEdges g (Node 0) [false; true].