Блог

Главная - Вопросы по программированию - Вставить тип в дерево F #

Вставить тип в дерево F #

#f#

#f#

Вопрос:

Я умудрился приготовить себе огромную миску спагетти и не могу найти выход. Я пытаюсь вставить тип в дерево и впоследствии изменить порядок расположения следующих деревьев.

Вот мои типы:

 type Government = {
    Id : Id;
    Name : string;
    Abbreviation : string;
    ParentId : string option;
}

type GovernmentStructure<'gov> = 
    | Root of Government : 'gov * SubGov : GovernmentStructure<'gov> list
    | Node of Government : 'gov * SubGov : GovernmentStructure<'gov> list
    | Leaf of Government : 'gov

а вот и спагетти, лол. Это не работает, но это показывает мозговой штурм, в который я попал.

 let insertGovernment (posGov: Government) (newGov : Government) (parentId : string)
    (currentStructure : GovernmentStructure<Government> list) =

    let rec reorderStructure (govPos : Government) (newGov : Government)
        (currentStructure : GovernmentStructure<Government>) =

        match currentStructure with
        | Root(gov', subGov) when gov' = govPos ->
            let rec updateSubGov parentId (movGov: Government) 
                (uSubGov : GovernmentStructure<Government> list) =
                [
                    Node({
                            Government.Id = movGov.Id;
                            Name = movGov.Name;
                            Abbreviation = movGov.Abbreviation;
                            ParentId = Some(parentId)
                        },[
                            for x in uSubGov do
                                match x with
                                | Node(g, s) -> yield! (updateSubGov movGov.Id g s)
                                | Leaf(g) -> yield x
                        ])
                ]


            Root(newGov, (updateSubGov newGov.Id gov' subGov)) 
        | node ->
            let rec updateStructure parentId (insGov : Government) 
                (node : GovernmentStructure<Government> list) =
                match node with
                | Root(gov', subGov) ->
                    Root(gov', [
                                for (x) in subGov do
                                    match x with
                                    | Node(g,s) when g = govPos ->  
                                        yield Node(insGov, updateStructure g.Id s )

                                    | Node(g,s) -> yield Node(g, updateStructure g.Id s)
                            ])
                | Node(gov', subGov) when gov' = govPos ->

                    [
                        Node({
                                Government.Id = insGov.Id;
                                Name = insGov.Name;
                                Abbreviation = insGov.Abbreviation;
                                ParentId = Some(parentId)
                            },[
                                for x in uSubGov do
                                    match x with
                                    | Node(g,s) -> yield Node(g, updateStructure movGov.Id g s)
                            ])
                    ]
                | Leaf(g) -> 
                    [
                        Node(newGov, [Leaf({
                                            g with ParentId = newGov.Id
                                        })])
                    ]
            node |> (fun x -> 
                            match x with
                            | Root(g,s) -> Node(g,(updateStructure g.Id g s))
                            | Node(g,s) -> Node(g,(updateStructure g.Id g s)))

Помогите!!! Я тону в соусе, лол.

Комментарии:

1. Быть более конкретным, чем не сработало

2. Не знаю, что вы подразумеваете под «не работает», но я заметил, что в вашем match выражении в updateStructure есть несоответствие типов. Ваш Root регистр возвращает один GovernmentStructure элемент (в частности, Root ), но ваши Node и Leaf регистры возвращают список GovernmentStructure элементов. В обоих случаях в этом списке есть только один элемент, так что вы могли бы изменить регистр, чтобы возвращать только Node вместо списка, и тогда match все совпадало бы (хех).

3. Также updateStructure говорится, что node параметром является GovernmentStructure list , но вы сопоставляете его с отдельными GovernmentStructure случаями. Это еще одно несоответствие типов.

Ответ №1:

Это решение, которое я смог придумать. Я бы не сомневался, что существует более эффективный ответ.

 let insertGovernment (posGov: Government) (newGov : Government)
(currentStructure : GovernmentStructure<Government>) =

let updateStructure (govPos : Government) (newGov : Government)
    (currentStructure : GovernmentStructure<Government>) =

    // iterate over the nodes to find position and insert. parentId is useless, will fix later 
    let rec findPosAndInsertInto parentId (startStructure : GovernmentStructure<Government>) =
        match startStructure with
        | Node (g, sg) when g = govPos ->
            Node(g, [
                            yield Node(newGov, [])
                            yield! sg
                        ])
        | Node (g, sg) ->
            Node (g, [
                        for x in sg do
                            yield findPosAndInsertInto g.Id x
                    ])
        | Leaf(g) when g = govPos -> 
            Node (g, [Leaf(newGov)])
        // better logic needed, should not hit this
        | node -> node

    match currentStructure with
    // Insert if position is at root
    | Root(gov', subGov) when gov' = govPos ->

        Root(gov', [    
                        yield Node(newGov, [])
                        yield! subGov
                    ]) 
    // Insert if position is at node or leaf
    | node -> 
        match node with
        | Root (gov', subGov) ->
            Root(gov', [
                        for x in subGov do
                            yield findPosAndInsertInto gov'.Id x 
                    ])
        // better logic needed, shouldn't hit this level
        | node -> node

updateStructure posGov newGov currentStructure