Updating a deeply nested array?

Learn
1

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:

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.

2

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.

3

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:

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.

4

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.

5

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)

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

6

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}
7

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

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.

8

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?

9

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