Вяз - дерево - добавить ветку к другому дереву - рекурсивный цикл

Question

Я хочу переместить ветви с дерева на дерево в Вязах.

Например:

Дерево 1:

A-1
- A-1-1
- - A-1-1-1
- - A-1-1-2
- - - A-1-1-2-1
- - - A-1-1-2-2

Дерево 2

B-1
- B-1-1
- - B-1-1-1
- - B-1-1-2
- - - B-1-1-2-1
- - - B-1-1-2-2

Я хотел бы переместить A-1-1 в B-1-1-2-1, что должно дать

B-1
- B-1-1
- - B-1-1-1
- - B-1-1-2
- - - B-1-1-2-1
- - - - A-1-1
- - - - - A-1-1-1
- - - - - A-1-1-2
- - - - - - A-1-1-2-1
- - - - - - A-1-1-2-2
- - - B-1-1-2-2

Я новичок вфункциональное программирование. Я могу представить, как это сделать с помощью рекурсивного цикла в Python, но я застрял с Elm.

Я могу легко переместить один узел, но не вижу, как рекурсивно добавить потомков:

module Main exposing (..)

import Canopy exposing (Node, append, children, leaf, mapChildren, node, value)
import Html exposing (Html, b, div, h1, h2, li, text, ul)
import List exposing (map)


tree1 : Node String
tree1 =
    node "A-1"
        [ node "A-1-1"
            [ leaf "A-1-1-1"
            , node "A-1-1-2"
                [ leaf "A-1-1-2-1"
                , leaf "A-1-1-2-2"
                ]
            ]
        ]


tree2 : Node String
tree2 =
    node "B-1"
        [ node "B-1-1"
            [ leaf "B-1-1-1"
            , node "B-1-1-2"
                [ leaf "B-1-1-2-1"
                , leaf "B-1-1-2-2"
                ]
            ]
        ]


tree3 : Node String
tree3 =
    let
        nodeToMove =
            "A-1-1"

        newParentNode =
            "B-1-1-2-1"

        -- append the node only but not its descendants
        treeWithNewNode =
            append newParentNode nodeToMove tree2

        -- type mismatch
        --        treeWithNewNodeAndNewNodeChildren =
        --            nodeToMove |> mapChildren (\child -> append 

        -- does not do what I was hopping for
        -- newTree =
        --    mapChildrenAt
        --        nodeToMove
        --        (\child -> append newParentNode (value child) treeWithNewNode)
        --        tree2

newParentNode child tree2)
    in
    treeWithNewNode


main =
    div []
        [ h1 [] [ text "Adding a branch to another tree" ]
        , h2 [] [ text "Tree 1" ]
        , viewNode tree1
        , h2 [] [ text "Tree 2" ]
        , viewNode tree2
        , h2 [] [ text "Move A-1-1 under B-1-1-2-1" ]
        , viewNode tree3
        ]


viewNode : Node String -> Html msg
viewNode node =
    let
        subNodes =
            children node
    in
    li []
        [ b [] [ text (value node) ]
        , ul [] (List.map viewNode subNodes)
        ]

Моя пробная версия здесь: https://ellie -app.com / 7842F8jCLpCa1

Я использую Canopy здесь, но я мог бы использовать другую библиотеку, если это рекомендуется.

Answer 1

В вашем коде мне кажется, что вы на самом деле никогда не извлекаете детей A-1-1 из tree1, поэтому давайте начнем с этого:

subtreeToMove =
    Maybe.withDefault (leaf <| "Failed to find node " ++ nodeToMove) <| get nodeToMove tree1

get Функция находит узел в дереве по значению. Поскольку не может быть узла с указанным значением, он возвращает Maybe, поэтому мы передаем значение по умолчанию.

Далее вы найдете целевой узел в tree2 и присоедините узел с егодети. Я буду использовать replaceChildrenAt здесь, поскольку целевой узел - это лист:

treeWithNewNode =
    tree2 |> replaceChildrenAt newParentNode [ subtreeToMove ]

Все готово!

Просто упомяните это, потому что вы описалижелаемый результат - перемещение узла между деревьями: все данные в Elm неизменны, поэтому после перемещения tree1 и tree2 остаются неизменными. Таким образом, поддерево из tree1 было скопировано в дубликат tree2

Answer 2

Мое решение без replaceChildrenAt для сохранения существующих детей.

module Main exposing (main)

import Canopy exposing (Node, append, children, get, leaf, node, value)
import Html exposing (Html, b, div, h1, h2, li, text, ul)



-- add a node (and its children) under a branch in another tree


tree1 : Node String
tree1 =
    node "A-1"
        [ node "A-1-1"
            [ leaf "A-1-1-1"
            , node "A-1-1-2"
                [ leaf "A-1-1-2-1"
                , leaf "A-1-1-2-2"
                ]
            ]
        ]


tree2 : Node String
tree2 =
    node "B-1"
        [ node "B-1-1"
            [ leaf "B-1-1-1"
            , node "B-1-1-2"
                [ node "B-1-1-2-1"
                    [ leaf "don't remove me"
                    ]
                , leaf "B-1-1-2-2"
                ]
            ]
        ]


tree3 : Node String
tree3 =
    let
        nodeToMove =
            Maybe.withDefault (leaf <| "Failed to find node " ++ "A-1-1") <| get "A-1-1" tree1

        newParentNodeValue =
            "B-1-1-2-1"

        treeWithNewNode =
            tree2 |> addNodeAt nodeToMove newParentNodeValue
    in
    treeWithNewNode



-- treeWithNewNode


main =
    div []
        [ h1 [] [ text "Adding a branch to another tree" ]
        , h2 [] [ text "Tree 1" ]
        , viewNode tree1
        , h2 [] [ text "Tree 2" ]
        , viewNode tree2
        , h2 [] [ text "Move A-1-1 under B-1-1-2-1" ]
        , viewNode tree3
        ]


viewNode : Node String -> Html msg
viewNode node =
    let
        subNodes =
            children node
    in
    li []
        [ b [] [ text (value node) ]
        , ul [] (List.map viewNode subNodes)
        ]


addNodeAt : Node String -> String -> Node String -> Node String
addNodeAt node firstParentNodeValue toTree =
    --Canopy.toList ->
    -- [("A-1-1",Nothing),("A-1-1-1",Just "A-1-1"),("A-1-1-2",Just "A-1-1"),...]
    node
        |> Canopy.toList
        |> List.foldl
            -- acc is the updated toTree
            (\( nodeValue, parentValue ) acc ->
                append
                    (Maybe.withDefault firstParentNodeValue parentValue)
                    nodeValue
                    acc
            )
            -- initial value
            toTree

Видно здесь: https://ellie -app.com / 79sd7H8fCjNa1

---

Ответ @ oo-balance: https://elmprogramming.com/list.html#folding-a-list мне очень помог.