如何在功能上编写具有依赖条件的动态更改集合的迭代算法？
How can iterative algorithm over a dynamically changed collection with depended condition be written functionally?
我有删除从指定节点开始并根据边标记输入列表的图的不可达节点的算法：
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)];}
它有效，但据我所知，我怀疑我的带引用的算法 clearEdges 很丑陋并且不是 F# 风格的。我曾尝试按功能编写它，但可能我已经接受了迭代算法和收集方法的混合。有什么实用的方法可以做到这一点吗？因为我认为丑陋的工作代码比没有代码更糟糕。谢谢。
正如其他人所建议的，您可能希望通过使用引用单元来删除重新分配，而是使用折叠或递归来累积一些状态。这是我想出的：
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)
您使用了一组边来表示您的图形。这防止了完全重复的边缘，但它仍然允许明显非法的状态：例如0 可以有两个传出 true 边到不同的节点。将您的图形表示为 (node, value) 到 node 的映射可能会更好。这也可以提高这种情况下的性能，因为您将利用地图的键查找。
请在生成的代码中记录此函数的作用及其原因！我花了一段时间才弄清楚发生了什么，因为我没想到 clearEdges 在删除传出边时会遍历具有两个中止条件的固定跃点列表。
您可以将数据结构更改为此，这会增加一些类型安全性并使遍历图更容易：
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 ]
那么，clearEdges可以这样写：
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
不需要更多功能。呼叫更改为 clearEdges g (Node 0) [false; true].
正如其他人在答案和评论中所说，回答这个问题最难的部分是理解代码。它缺乏很好的描述和评论。
我为理解代码所做的第一件事是添加类型签名，然后向您的代码添加 printfn 语句以查看它在做什么。
之后因为更容易理解问题中的代码。
在重新设计代码时，我并没有尝试一次更改小部分，而是根据我从 printfn 输出和类型签名中学到的知识，从头开始构建核心功能。我毫不犹豫地从使用 ref 的可变代码切换到在每个函数中从头开始重建的不可变图。每次丢弃现有数据结构并构建一个新数据结构似乎是一种浪费，但请这样想：必须在每条边上做出决定的函数必须访问每条边，因此当您访问每条边时您可以将它添加到新图形中，也可以不添加它，这使得编码变得更容易，对于其他试图理解它的人来说也更容易。
我还添加了类型以使类型签名更有意义并使代码的作用更加清晰。一点点工作的大红利。
然后我查看了函数，而不是专注于使代码尽可能简洁，而是专注于可读性和可维护性，并分解了一个函数以使其更明显。
显然这个答案比其他两个更长，但比原始代码更实用，没有可变因素，第一次阅读时更容易理解，并注释以解释每个函数的作用。
如果这是库的一部分，则应修改代码以删除类型签名，如果这是通用的，那将不是一个选项。还使单独的函数成为内部函数并将其中的一些重构下来以使用内置的 F# 核心函数并添加更多注释以补偿这样做时的清晰度损失。
在早期版本中，我尽可能使用 List.pick but realized it could throw a KeyNotFoundException exception and since I like my functions to be total 修改它以避免异常。
在查看我的回答时，我对 if not (nodeUsed graph node) then 不满意；这是简单中的一个疣。所以我决定求助于函数式编程这把瑞士军刀：factoring. Pure functional programming is basically expressions that can be factored like math expressions, or more theoretically term rewriting。我知道如果我可以分解出带有 not 的线，我可以使它更漂亮并且更容易理解。所以分解 not 的方法是将它移到 let rec 之外，例如pathToNodes，这可以通过传入节点列表而不是转换列表来完成，例如reduceGraph2。一旦完成，代码就变得简单了。
我相信人们可以进一步简化代码，但我通常会像这样为 F# 新手留下我的答案，因为他们更容易理解。
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
我有删除从指定节点开始并根据边标记输入列表的图的不可达节点的算法：
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)];}
它有效，但据我所知，我怀疑我的带引用的算法 clearEdges 很丑陋并且不是 F# 风格的。我曾尝试按功能编写它，但可能我已经接受了迭代算法和收集方法的混合。有什么实用的方法可以做到这一点吗？因为我认为丑陋的工作代码比没有代码更糟糕。谢谢。
正如其他人所建议的，您可能希望通过使用引用单元来删除重新分配，而是使用折叠或递归来累积一些状态。这是我想出的：
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)
您使用了一组边来表示您的图形。这防止了完全重复的边缘，但它仍然允许明显非法的状态：例如0 可以有两个传出 true 边到不同的节点。将您的图形表示为 (node, value) 到 node 的映射可能会更好。这也可以提高这种情况下的性能，因为您将利用地图的键查找。
请在生成的代码中记录此函数的作用及其原因！我花了一段时间才弄清楚发生了什么，因为我没想到 clearEdges 在删除传出边时会遍历具有两个中止条件的固定跃点列表。
您可以将数据结构更改为此，这会增加一些类型安全性并使遍历图更容易：
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 ]
那么，clearEdges可以这样写：
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
不需要更多功能。呼叫更改为 clearEdges g (Node 0) [false; true].
正如其他人在答案和评论中所说，回答这个问题最难的部分是理解代码。它缺乏很好的描述和评论。
我为理解代码所做的第一件事是添加类型签名，然后向您的代码添加 printfn 语句以查看它在做什么。
之后因为更容易理解问题中的代码。
在重新设计代码时，我并没有尝试一次更改小部分，而是根据我从 printfn 输出和类型签名中学到的知识，从头开始构建核心功能。我毫不犹豫地从使用 ref 的可变代码切换到在每个函数中从头开始重建的不可变图。每次丢弃现有数据结构并构建一个新数据结构似乎是一种浪费，但请这样想：必须在每条边上做出决定的函数必须访问每条边，因此当您访问每条边时您可以将它添加到新图形中，也可以不添加它，这使得编码变得更容易，对于其他试图理解它的人来说也更容易。
我还添加了类型以使类型签名更有意义并使代码的作用更加清晰。一点点工作的大红利。
然后我查看了函数，而不是专注于使代码尽可能简洁，而是专注于可读性和可维护性，并分解了一个函数以使其更明显。
显然这个答案比其他两个更长，但比原始代码更实用，没有可变因素，第一次阅读时更容易理解，并注释以解释每个函数的作用。
如果这是库的一部分，则应修改代码以删除类型签名，如果这是通用的，那将不是一个选项。还使单独的函数成为内部函数并将其中的一些重构下来以使用内置的 F# 核心函数并添加更多注释以补偿这样做时的清晰度损失。
在早期版本中，我尽可能使用 List.pick but realized it could throw a KeyNotFoundException exception and since I like my functions to be total 修改它以避免异常。
在查看我的回答时，我对 if not (nodeUsed graph node) then 不满意；这是简单中的一个疣。所以我决定求助于函数式编程这把瑞士军刀：factoring. Pure functional programming is basically expressions that can be factored like math expressions, or more theoretically term rewriting。我知道如果我可以分解出带有 not 的线，我可以使它更漂亮并且更容易理解。所以分解 not 的方法是将它移到 let rec 之外，例如pathToNodes，这可以通过传入节点列表而不是转换列表来完成，例如reduceGraph2。一旦完成，代码就变得简单了。
我相信人们可以进一步简化代码，但我通常会像这样为 F# 新手留下我的答案，因为他们更容易理解。
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