具有依赖条件的动态变化集合的迭代算法如何在功能上进行编写？

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异常,因为我喜欢我的职务是总时可能修改,以避免例外.

在看我的回答时,我并不满意if not (nodeUsed graph node) then; 这是一个简单中间的疣.所以我决定采用功能性编程的旧瑞士军刀:保理.纯函数式编程基本上是可以像数学表达式一样考虑的表达式,或者理论上更多的术语重写.我知道如果我可以把它排成一线,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

Answer 2

请在结果代码中记录此功能正在做什么以及为什么!我花了一段时间来弄清楚发生了什么,因为我没想到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].