Aktualizacja wartości w typie rekurencyjnej - wiąz lang

Question

Mam strukturę drzewa węzłów tekstowych, które mogą mieć inny węzły tekstowe jak dzieci, i muszę zaktualizować jedną wartość w nim. Jaki jest najłatwiejszy sposób aktualizacji węzła tekstowego, który znajduje się gdzieś głęboko w tym drzewie (lub w ogóle nie jest w tym drzewie)?

w języku non-niezmiennej, chciałbym po prostu zmienić wartość tej pozycji, i to wszystko, ale jest to dość trudne w niezmiennej języku jak Elm.

type alias Item = 
    { id: String 
    , text: String 
    , children: ChildItems 
    } 

type ChildItems = ChildItems (List Item) 

type alias Model = 
    { rootItem: Item 
    } 

updateItem: Item -> Item -> Item 
updateItem: rootItem item = 
    -- TODO 

... 

update model = 
    case msg of 
    UpdateItem item updatedText -> 
     let 
     updatedItem = { item | text = updatedText } 
     in 
     ({ model | rootItem = (updateItem model.rootItem updatedItem) }, Cmd.none) 

to co wymyśliłem

updateItem: Item.Item -> Item.Item -> Item.Item 
updateItem rootItem updatedItem = 
    if rootItem.id == updatedItem.id then 
    updatedItem 
    else 
    case rootItem.children of 
     Item.ChildItem [] -> 
     rootItem 

     Item.ChildItem children -> 
     let 
      updatedChildren = 
      case children of 
       [] -> 
       [] 

       children -> 
       List.map (\item -> 
        updateItem rootItem item) children 
     in 
      { rootItem | children = Item.ChildItem updatedChildren } 

ale dostaję błąd Maximum call stack size exceeded

Answer 1

Powodem dostajesz przepełnienie stosu jest dlatego, że zamiast wracać rootItem[] w przypadku Item.ChildItems [].

mam zamiar zmodyfikować kod trochę ponieważ istnieją pewne wspólne wzorce możemy wyciągnąć na zewnątrz. Po pierwsze, weźmy pod spodem drzewo-owski strukturę i sprawiają, że bardziej ogólny, aby mogła ona pasuje do każdego typu rzeczy, nie tylko Item:

type Node a 
    = Node a (List (Node a)) 

To daje nam strukturę, która zawsze ma węzła głównego i może mieć dowolną liczbę dzieci, z których każda może mieć dowolną liczbę dzieci.

Jeśli myślimy o algorytmie Miałeś na, możemy ekstrapolować znajomy wzór. Masz strukturę z wieloma elementami i chcesz mieć algorytm, który odwiedza każdy element i opcjonalnie go zmienia. Brzmi bardzo podobnie do List.map. To taki wspólny idiom, że to dobry pomysł, aby zadzwonić nasza uogólniona funkcja map:

map : (a -> b) -> Node a -> Node b 
map f (Node item children) = 
    Node (f item) (List.map (map f) children) 

(uwaga Side: Właśnie natknął się functors!)

Ponieważ wziąłem pomysł dzieci i umieścił ją w rodzaju Node, musimy zmodyfikować alias Item tak:

type alias Item = 
    { id: String 
    , text: String 
    } 

teraz mamy Item, pomocne będzie posiadanie funkcji, która może ją zaktualizować, jeśli wartość id pasuje do określonej wartości. Ponieważ w przyszłości może mieć więcej funkcji aktualizacji, które chcesz wykonać, to najlepiej, aby utrzymać część odnośnika i pasujący ID oddzielone od funkcji, którą rzeczywiście chcesz wykonać:

updateByID : String -> (Item -> Item) -> Item -> Item 
updateByID id f item = 
    if item.id == id then 
    f item 
    else 
    item 

teraz, aby wykonać aktualizację na zasadzie element odpowiadający identyfikatorowi, w dowolnym miejscu w drzewie, można to zrobić po prostu:

map (updateByID "someID" (\x -> { x | text = "Woohoo!" })) rootNode