How can I write a functional algorithm over a dynamically modified collection with a dependent condition?

Question

I have an algorithm that removes unreachable nodes of a graph, starting from the specified node and in accordance with entering the list of edges:

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

This works, but I suspect my clearEdges algorithm with links is ugly and not F # -styled as I understand it. I tried to write it functionally, but I probably got a mixture of iterative algorithm and collection methods. Is there any functional approach? Because I think ugly working code is worse than code. Thanks.

Answer 1

As others have said in answers and comments, the hardest part of answering this is understanding the code. There is no good description and comments in it.

The first thing I did to understand the code was to add printfn type and expression printfn to your code to see what it does.

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

When redesigning the code, I did not try to change small details at the same time, but I started from scratch, creating basic functions based on what I learned from printfn output printfn and types. Without hesitation, I switched from mutable code with ref to an immutable graph that was rebuilt from scratch in every function. It may seem like a waste to throw out the existing data structure and build a new one each time, but think about it this way: the functions that must make decisions at each edge should visit each edge, so when you visit each edge you either add it on a new chart, or don’t do it, which greatly simplifies its coding, and also much easier if others are trying to understand it.

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

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

It is clear that this answer is longer than the other two, but more functional than the source code, does not change, it is easier to understand on first reading and commented to explain what each function does.

If this should be part of the library, the code should be modified to remove type signatures, and if it is shared, that will not be an option. Also make separate functions of the internal functions and edit some of them to use the built-in functions of the F # kernel, and add more comments to compensate for the loss of clarity.

In an earlier version, I used List.pick , but realized that it could throw a KeyNotFoundException , and since I like my total functions, if possible, change it to avoid the exception.

When looking at my answer, I was unhappy if not (nodeUsed graph node) then ; it was a wart in the midst of simplicity. Therefore, I decided to resort to the old Swiss army knife of functional programming: factoring . Purely functional programming is basically an expression that can be considered mathematical expression, or more theoretically rewriting terms . I knew that if I could talk about the line with not , I could make it more beautiful, and that’s easier to understand. So the way to split the not was to move it outside of let rec , for example. pathToNodes , and this can be done by passing in a list of nodes instead of a jump list, for example. reduceGraph2 . Once this was done, the code achieved simplicity.

I am sure that the code can be more compensated, but I usually leave my answers, like this for new F # people, because they are easier to understand.

 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 write in your resulting code what this function does and why! It took me a while to figure out what was happening, as I did not expect clearEdges go through a fixed jump list with two interrupt conditions when deleting outgoing edges.

You can change the data structure to this, which adds some type safety and makes it easier to move the chart:

 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 as follows:

 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 

without additional features. The call changes to clearEdges g (Node 0) [false; true] clearEdges g (Node 0) [false; true] .

Answer 3

As suggested by others, you probably want to remove the reassignment using the ref cell and instead accumulate some state using bend or recursion. Here is what I came up with:

 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) 

You used a set of edges to represent your graph. This prevents a completely duplicated edge, but still allows for apparently illegal states: for example, 0 can have two outgoing true edges for different nodes. It might be better to present your chart as a map from (node, value) to node . It can also improve performance for this case, because you will use key search.