recursion - 如何在功能上编写针对具有依赖条件的动态更改集合的迭代算法？

Question

我有一种算法，可以根据边缘标记的输入列表删除从指定节点开始的图的不可达节点:

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# 风格的。我尝试过以函数方式编写它，但可能我已经收到了迭代算法和收集方法的混合。有没有任何函数式方法可以做到这一点？因为我认为丑陋的工作代码比没有代码更糟糕。谢谢。

Answer 1

正如其他人在答案和评论中所说，回答这个问题最困难的部分是理解代码。它缺乏良好的描述和评论。

为了理解代码，我做的第一件事就是添加类型签名，然后将 printfn 语句添加到代码中，以查看它在做什么。

之后，因为更容易理解问题中的代码。

在重新设计代码时，我并没有尝试一次更改一小部分，而是根据我从 printfn 输出和类型签名中学到的知识从头开始构建核心功能。我毫不犹豫地从使用 ref 的可变代码切换到在每个函数中从头开始重建的不可变图。扔掉现有的数据结构并每次构建一个新的数据结构似乎是一种浪费，但请这样考虑:必须在每个边缘上做出决策的函数必须访问每个边缘，因此当您访问每个边缘时您可以将其添加到新图表中，也可以不添加，这使得编码变得更加容易，并且对于其他试图理解它的人来说也更加容易。

我还添加了类型，以使类型签名更有意义，并让代码的功能更加清晰。一点点工作就能得到巨大的奖励。

然后，我查看了这些函数，并没有专注于使代码尽可能简洁，而是专注于可读性和可维护性，并分解了一个函数以使其更加明显。

显然这个答案比其他两个更长，但比原始代码更实用，没有可变的，第一次阅读时更容易理解，并注释了每个函数的作用。

如果这是库的一部分，则应修改代码以删除类型签名，如果这是通用的，则不可以选择。还要将单独的函数设为内部函数，并重构其中的一些函数以利用内置的 F# 核心函数，并添加更多注释以弥补这样做时的清晰度损失。

在早期版本中，我使用 List.pick但意识到它可能会抛出 KeyNotFoundException 异常，因为我喜欢我的函数是 total如果可能的话对其进行修改以避免异常。

在查看我的答案时，我对if not (nodeUsed graph node) then 不满意；这是简单中的一个疣。所以我决定求助于函数式编程这把古老的瑞士军刀:factoring 。 Pure functional编程基本上是可以像数学表达式一样分解的表达式，或者更理论上 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