# Updating a deeply nested array?

**URL:** <https://discourse.elm-lang.org/t/updating-a-deeply-nested-array/7928>\
**Category:** Learn\
**Created:** [November 21, 2021, 12:55pm UTC](https://discourse.elm-lang.org/t/updating-a-deeply-nested-array/7928 "2021-11-21T12:55:37Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Snaker](https://avatars.discourse-cdn.com/v4/letter/s/dfb087/32.png) [@Snaker](https://discourse.elm-lang.org/u/Snaker)\
**Post date:** [November 21, 2021, 12:55pm UTC](https://discourse.elm-lang.org/t/updating-a-deeply-nested-array/7928/1 "2021-11-21T12:55:38Z")

</div>

So I have some model where I want to update a value that is dynamically created and for which I can not know the depth beforehand.

My model is basically a representation of a Abstract Syntax Tree for a programming language but that shouldn’t matter much:

```auto
type alias CallExpression =
    { id: String
    , arguments: List Expression    
    }
type Expression
    = Call CallExpression
    | ToDo
    | NumberLiteral Float
    
type alias Model =
    { ast : Array Expression
    , -- Some other stuff
    }

```

Now imagine a certain input field was printed that represents the value of a NumberLiteral inside the AST. How would I go about updating the model and change that specific NumberLiteral on user input?

(Something like the two-way binding in VueJs would help in that case but it needs it to be more general)

My only idea is to flatten the whole structure using Dictionaries to avoid the nesting but that would take me much further away from I am actually trying to represent.

---

<div class="post-metadata">

**Author:** ![wondible](https://avatars.discourse-cdn.com/v4/letter/w/e9c0ed/32.png) [@wondible](https://discourse.elm-lang.org/u/wondible)\
**Post date:** [November 21, 2021, 1:38pm UTC](https://discourse.elm-lang.org/t/updating-a-deeply-nested-array/7928/2 "2021-11-21T13:38:30Z")

</div>

I frequently create a function which maps the data structure, returning the same node for all entries except the one I want to change. You need some way to address the target node though. If your structure is stable enough, you can record the array indexes of each level. Depending on how you are deciding which number to edit, you might also be able put an invisible id node around that expression.

---

<div class="post-metadata">

**Author:** ![Carsten\_Konig](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/carsten_konig/32/4063_2.png) [@Carsten\_Konig](https://discourse.elm-lang.org/u/Carsten_Konig)\
**Post date:** [November 22, 2021, 10:54am UTC](https://discourse.elm-lang.org/t/updating-a-deeply-nested-array/7928/3 "2021-11-22T10:54:20Z")

</div>

For a recursive/tree-like structure you first have to figure out how to get an index-like value.

I can think of those alternatives:

- every node in your tree/graph has an identity and you have a way to decide on each level where to look next for this identity (for example (binary-)search-trees with their keys
- the index is the _path_ to the node - this is often used in computer-science and it basically works every time but it might have a bad user-XP or runtime

Anyway the the path-Idee could look like this:

```elm
type ExpressionPath = Here | GotoCallArgument Int ExpressionPath

changeNumberValue : ExpressionPath -> Float -> Expression -> Expression
changeNumberValue path newValue expr =
    case (path, expr) of
        (Here, NumberLiteral _) -> NumberLiteral newValue
        (GotoCallArgument n cont, Call callExpressions) ->
            callExpressions
            |> List.indexedMap (\index subExpr ->
                if index == n then changeNumberValue cont newValue subExpr else subExpr)
            |> Call
        -- the path was invalid - this one takes the easy way out - extent for errors/Maybe if you like
        _ -> expr

```

of course you’ll have to write a `find` that’ll return a valid path to use this

* * *

PS: maybe Elm here is not the best language for these problems or you might want to rethink your approach. I’d try and not change the AST - an AST is probably only some intermediate form and maybe you can write your interpreter in a way where a user input means updating a dictionary (if you want the _memory_ of you machine/interpreter).  
Otherwise I think this is going to be really slow as you are probably constantly searching/changing leaves in your tree which will replace a large portion of the AST.

---

<div class="post-metadata">

**Author:** ![Snaker](https://avatars.discourse-cdn.com/v4/letter/s/dfb087/32.png) [@Snaker](https://discourse.elm-lang.org/u/Snaker)\
**Post date:** [November 22, 2021, 1:38pm UTC](https://discourse.elm-lang.org/t/updating-a-deeply-nested-array/7928/4 "2021-11-22T13:38:53Z")

</div>

> [@Carsten\_Konig](#):
>
> Otherwise I think this is going to be really slow as you are probably constantly searching/changing leaves in your tree which will replace a large portion of the AST.

Yeah, I am very worried about this. I absolutely need too edit the the AST directly, constantly and in real time.

I think finding should be pretty performant. Worst case would be like linear time, right? The the path idea is probably a bit better. Of course I am a bit worried about the updating itself, I don’t think Elm is able to optimize it into in place mutation so lots of copying around. The more the AST grows, the worse it gets.

I am not really aware of an language that would help a great deal here. An imperative solution might of course be quite a bit better.

For now I will try your solution and and see how it goes.

---

<div class="post-metadata">

**Author:** ![Carsten\_Konig](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/carsten_konig/32/4063_2.png) [@Carsten\_Konig](https://discourse.elm-lang.org/u/Carsten_Konig)\
**Post date:** [November 22, 2021, 2:08pm UTC](https://discourse.elm-lang.org/t/updating-a-deeply-nested-array/7928/5 "2021-11-22T14:08:13Z")

</div>

You could use ports and handle the mutation in JS but I don’t think that’s a fun/good way to do it.

In most FP languages you have Refs to handle stuff like this and there are Elm packages doing similar stuff (for example this one here: [elm-reference 1.0.7](https://package.elm-lang.org/packages/arowM/elm-reference/latest/))

Never used those in Elm so I cannot say anything about runtime/tradeoffs but it might be worth a try.

---

<div class="post-metadata">

**Author:** ![AvailableUsername](https://avatars.discourse-cdn.com/v4/letter/a/cc9497/32.png) [@AvailableUsername](https://discourse.elm-lang.org/u/AvailableUsername)\
**Post date:** [November 22, 2021, 4:04pm UTC](https://discourse.elm-lang.org/t/updating-a-deeply-nested-array/7928/6 "2021-11-22T16:04:45Z")

</div>

I think the problem is that you have no way to represent variables in your syntax trees.  
You could add variables to your Expression type.

```
type Expression
    = Call CallExpression
    | Todo
    | NumberLiteral Float
    | Variable String

```

or, even, if you have a small number of possible variables (say, X and Y):

```
type Expression
    = Call CallExpression
    | Todo
    | NumberLiteral Float
    | X
    | Y

```

Then maintain a mapping of variables to values and use that mapping when doing computations with your trees.

In the first case (variables as strings):

```
type alias Mapping = Dict String Float

```

In the second case (just two variables X and Y):

```
type alias Mapping = { x: Float, y: Float}
```

---

<div class="post-metadata">

**Author:** ![Snaker](https://avatars.discourse-cdn.com/v4/letter/s/dfb087/32.png) [@Snaker](https://discourse.elm-lang.org/u/Snaker)\
**Post date:** [November 22, 2021, 4:36pm UTC](https://discourse.elm-lang.org/t/updating-a-deeply-nested-array/7928/7 "2021-11-22T16:36:55Z")

</div>

> [@Carsten\_Konig](#):
>
> In most FP languages you have Refs to handle stuff like this and there are Elm packages doing similar stuff (for example this one here: [elm-reference 1.0.7](https://package.elm-lang.org/packages/arowM/elm-reference/latest/))

This looks great. I can’t imagine it helping performance much but at least should make the task much easier.

> [@AvailableUsername](#):
>
> I think the problem is that you have no way to represent variables in your syntax trees.  
> You could add variables to your Expression type.

Oh that is exactly how I implemented variables, nice to see I am on the right track. I did leave out this part though for simplicity sake.

No, I explicitly want to modify the NumberLiteral and that is just the start. I need to be able to do all sorts of complex modifications to the AST in real time, deleting and moving nodes and so on. (If you need to know, it is similar to what the editor of the Roc programming language does, allowing you to edit the language directly in AST form. At least from what I can tell from the videos.)

I think it might be better to think about me wanting to writer an editor for a complex ToDo List with child elements or something like this, which would require similar solutions.

---

<div class="post-metadata">

**Author:** ![pit](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/pit/32/5389_2.png) [@pit](https://discourse.elm-lang.org/u/pit)\
**Post date:** [November 23, 2021, 6:42am UTC](https://discourse.elm-lang.org/t/updating-a-deeply-nested-array/7928/8 "2021-11-23T06:42:58Z")

</div>

If you are always editing one node at a time, you could use a tree zipper to focus on the currently edited node. Then most of the work would be spent on moving the focus, but not on editing the current node. Maybe this is better in your use case?

---

<div class="post-metadata">

**Author:** ![system](https://canada1.discourse-cdn.com/flex035/uploads/elm_lang/original/1X/50a05e53677a2c3b47776d7abd0f113eb50193a1.png) [@system](https://discourse.elm-lang.org/u/system)\
**Post date:** [December 3, 2021, 6:43am UTC](https://discourse.elm-lang.org/t/updating-a-deeply-nested-array/7928/9 "2021-12-03T06:43:04Z")

</div>

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.