Update value in a recursive type - elm lang

Question

I have a tree like structure of text nodes that might have another text nodes as children, and I need to update one value in it. What's the easiest way to update text node that's somewhere deep in that tree (or it is not in that tree at all)?

In a non-immutable language, I would simply change a value of that item, and that's it, but it's quite tricky in an immutable language like 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)

this is what I came up with

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 }

but I'm getting an Maximum call stack size exceeded error

Answer 1

The reason you're getting the stack overflow is because you are returning rootItem instead of [] in the Item.ChildItems [] case.

I'm going to modify your code a bit because there are some common patterns we can pull out. First off, let's take the underlying tree-ish structure and make that more generic so that it could fit any type of thing, not just Item:

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

That gives us a structure that always has a root node and may have any number of children, each of who may also have any number of children.

If we think about the algorithm you were going for, we can extrapolate a familiar pattern. You have a structure with multiple items and you want an algorithm that visits each item and optionally changes it. That sounds a lot like List.map. It's such a common idiom that it's a good idea to call our generalized function map:

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

(Side note: We've just stumbled into functors!)

Since I've taken the idea of children and placed it into the Node type, we need to modify the alias Item like so:

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

Now that we have an Item, it will be helpful to have a function that can update it if the id matches a certain value. Since in the future, you may have more update functions you want to perform, it's best to keep the lookup and ID matching portion separate from the function you actually want to perform:

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

Now to perform an update on an item matching the id, anywhere within the tree, you can simply do this:

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