Update value in recursive type - elm lang

Question

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

In an immutable language, I would just change the value of this element and that, but it is rather complicated in an immutable language such as 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) 

that's 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 get the error Maximum call stack size exceeded

Answer 1

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

I will change my code a bit because there are some common patterns that we can pull out. First of all, let’s take the basic structure of the tree and make it more general so that it can correspond to any type of thing, and not just Item :

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

This gives us a structure that always has a root node and can have any number of children, each of which can also have any number of children.

If we think about the algorithm you were looking for, we can extrapolate the familiar pattern. You have a structure with several elements, and you need an algorithm that visits each element and possibly changes it. This is very similar to List.map . This is such a common idiom that it’s nice to call our generalized map function:

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

(Side note: we just stumbled upon functors !)

Since I accepted the idea of ​​children and put it in a Node type, we need to change the Item alias as follows:

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

Now that we have Item , it will be useful to have a function that can update it if id matches a specific value. Since in the future you may have more update functions that you want to perform, it is best to separate the search and identifier area from the function that you really want to perform:

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

Now, to update the element corresponding to the identifier anywhere in the tree, you can simply do this:

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