Как смоделировать простую иерархию с одним корнем

Question

Я хочу смоделировать иерархию в F #, где каждый узел должен иметь одного родителя, за исключением, очевидно, корневого узла, у которого нет родителя.Мое наивное решение

type Node = {
    Id: int // meta data for node
    Parent: Node option
}
let root = { Id = 1; Parent = None}
let child1 = { Id = 2; Parent = Some(root)}
let child2 = { Id = 3; Parent = Some(child1)}

Но мой вход в F # был через @swlaschin, и он взорвал мои мысли созданием описательных доменов.Так что мне воняет, что Parent - вариант, когда требуется 99% времени.Мои лучшие усилия:

type Node = 
    | Node of NodeMeta * Node
    | Root of NodeMeta
and NodeMeta = {
    Id: int
}
let root = Root({Id = 1})
let child1 = Node({Id = 2}, root)
let child2 = Node({Id = 3}, child1)

Есть ли более идиоматический способ?

Answer 1

Чисто функциональный идиоматический способ генерирования дерева - это использовать дерево <'a> без ссылки на родителя .... дерево ... - это дерево, свойство "parent" получается изпотомок существующего узла.

Затем вы используете Zipper для перемещения по дереву от родителя к потомку и от потомка к родителю ... скорее как «курсор» в списке элементов.

см. http://tomasp.net/blog/tree-zipper-query.aspx/

Вы можете, если хотите, создать свое собственное дерево с различными корневыми и некорневыми типами, где только существующие не корни могут быть добавлены к существующим узлам.Тогда вам, вероятно, придется также свернуть свою собственную молнию, поэтому ее стоимость высока.

Answer 2

Если бы я строил это для своей собственной модели в доменно-управляемой схеме, я бы, вероятно, определил узлы следующим образом:

[<Struct>] type NodeId = private NodeId of int

module NodeId =
    let create id =
        // Replace with the proper validation rules for a Node Id
        if id < 0
        then Error "NodeId must be non-negative" // I would actually use a DU with each error case
        else Ok <| NodeId id

    let value (NodeId id) = id

type [<Struct>] RootNode = {Id: NodeId}
type [<Struct>] ChildNode = {Parent: Node; Id: NodeId}

and Node =
    | Root of RootNode
    | Node of ChildNode
    member node.Id =
        match node with
        | Root r -> r.Id
        | Node n -> n.Id
    member node.Parent =
        match node with
        | Root _ -> None
        | Node n -> Some n.Parent
    member node.IsRootNode =
        match node with
        | Root _ -> true
        | Node _ -> false
    member node.IsChildNode = 
        not node.IsRootNode

Это дает нам следующее:

• Тип для NodeId, охватывающий int, и сопровождающий модуль, который инкапсулирует любые бизнес-правила, определяющие, что делает действительным идентификатором
• Определенные типы для RootNode и ChildNode, которые позволяют им иметь толькообязательные поля для этого типа узла
• Единственный тип Node, который позволяет нам представлять RootNode и ChildNode как один и тот же тип, не требуя, чтобы они имели те же поля, но при этом предоставляя прямой доступ клежащие в основе поля и позволяющие нам легко различать RootNode s и ChildNode s

Тогда у меня будет модуль для создания Node s, например:

module Node = 
    let createRoot = 
        NodeId.create >> Result.bind((fun id -> Root {Id = id}) >> Ok)

    let createChild parent =
        NodeId.create >> Result.bind((fun id -> Node {Id = id; Parent = parent}) >> Ok)