f# - 使用不可变列表创建具有链接节点的邻接列表

Question

我正在尝试创建一个包含当前定义如下的链接节点的邻接列表:

type Node =
    {
        Name: string
        Neighbors: Node list
    }

type AdjacencyList(nodes: Node list) =

    interface IHasNodes with
        /// Gets the number of nodes in the adjacency list.
        member this.NodeCount = nodes.Length

        /// Gets a list of all nodes in the adjacency list.
        member this.Nodes = nodes

我要从中创建列表的输入是格式为的字符串序列

node_name neighbor_name_1 ... neighbor_name_n

所以，基本上这应该是一个简单的任务，但我想不出一种方法来更新节点而不会在一个节点运行时进入循环，例如A，有一条到 B 的边，B 有一条到 A 的边。在这种情况下，我必须在创建其节点对象时更新 B 的邻居，然后将节点 A 中的邻居引用更新为节点 B，这又让我离开再次更新节点 B 等等。

module List =

    /// <summary>
    /// Replaces the first item in a list that matches the given predicate.
    /// </summary>
    /// <param name="predicate">The predicate for the item to replace.</param>
    /// <param name="item">The replacement item.</param>
    /// <param name="list">The list in which to replace the item.</param>
    /// <returns>A new list with the first item that matches <paramref name="predicate"/> replaced by <paramref name="item"/>.</returns>
    let replace predicate item list =
        let rec replaceItem remainingItems resultList =
            match remainingItems with
            | []         ->  resultList |> List.rev
            | head::tail ->
                match predicate(head) with
                | false -> replaceItem tail (head::resultList)
                | true  -> (item::resultList |> List.rev) @ tail

        replaceItem list []

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module AdjacencyList =

    let create (rows: seq<string>) =
        let mutable preBuiltNodes: Node list = []
        let rowsToEnumerate = rows |> Seq.where (fun str -> not (System.String.IsNullOrWhiteSpace(str)) || not (str.StartsWith("//")))
        let neighborsForNodes = Dictionary<string, string array>()

        // Build the base nodes and get the neighbors of each node.
        for row in rowsToEnumerate do
            let rowData = row.Split(' ')

            neighborsForNodes.Add(rowData.[0], rowData |> Array.skip 1)
            preBuiltNodes <- { Name = rowData.[0]; Neighbors = [] } :: preBuiltNodes

        // Build the final nodes from the pre-built nodes.
        let rec buildAdjacencyList remainingNodes (builtNodes: Node list) =
            match remainingNodes with
            | []         -> builtNodes
            | head::tail ->
                let neighbors = preBuiltNodes |> List.where (fun node -> neighborsForNodes.[head.Name] |> Array.exists (fun name -> name = node.Name))
                let newNode = { head with Neighbors = neighbors };

                // Update nodes referencing an old version of the new node.
                let mutable newBuiltNodes: Node list = []

                for i = 0 to (builtNodes.Length - 1) do
                    if builtNodes.[i].Neighbors |> List.exists (fun node -> node.Name = head.Name) then
                        let updatedNode = { builtNodes.[i] with Neighbors = builtNodes.[i].Neighbors |> List.replace (fun n -> n.Name = newNode.Name) newNode }
                        newBuiltNodes <- updatedNode :: newBuiltNodes

                        // Cycle here when updating newNode
                        // if it has an edge to the node at builtNodes.[i]

                    else
                        newBuiltNodes <- builtNodes.[i] :: newBuiltNodes

                preBuiltNodes <- preBuiltNodes |> List.replace (fun n -> n.Name = newNode.Name) newNode
                buildAdjacencyList tail (newNode::newBuiltNodes)

        buildAdjacencyList preBuiltNodes [] |> AdjacencyList

我之前已经在 C# 中实现了该算法(使用可变列表)，所以我在这里可能遗漏了一点。当然我也可以使用可变列表，但我想尝试使用不可变列表。

Answer 1

我认为没有任何方法可以用您的确切表示做您想做的事。一个简单的替代方法是让邻居集合变得懒惰:

type node<'a> = {
    id : 'a
    neighbors : Lazy<node<'a> list>
}

let convert (m:Map<'a, 'a list>) =
    let rec nodes = [
        for KeyValue(k,vs) in m -> 
            { id = k; 
              neighbors = lazy 
                            vs 
                            |> List.map (fun id -> 
                                            nodes 
                                            |> List.find (fun n -> n.id = id))}]
    nodes

convert (Map [1,[2;3]; 2,[3]; 3,[1]])

关键是通过使邻居列表变得惰性，我们可以首先创建我们关心的所有节点的集合，然后填充邻居集合(邻居计算 在创建节点的同时指定，但直到稍后才运行)。