Is there a more efficient way to update an element in a list in Elm than maping over each element?

{ model | items = List.indexedMap (\i x -> if i == 2 then "z" else x) model.items }

Maybe Elm's compiler is sophisticated enough to optimize this so that map or indexedMap isn't unnecessarily copying over every element except 1. What about nested lists?

Clojure has assoc-in to update an element inside a nested list or record (can be combined too). Does Elm have an equivalent?

CodePudding user response：

More efficient in terms of amount of code would be (this is similar to @MichaelKohl's answer):

List.take n list    newN :: List.drop (n 1) list

PS: if n is < 0 or n > (length of list - 1) then the new item will be added before or at the end of the list.

PPS: I seem to recall that a :: alist is slightly better performing than [a] alist.

If you mean efficient in terms of performance/ number of operations:

As soon as your lists get large, it is more efficient to use an Array (or a Dict) instead of a List as your type.

But there is a trade-off:

• Array and Dict are very efficient/ performant when you frequently retrieve/ update/ add items.
• List is very performant when you do frequent sorting and filtering and other operations where you actually need to map over the entire set.

That is why in my code, List is what I use a lot in view code. On the data side (in my update functions) I use Dict and Array more.

CodePudding user response：

Basically, an Elm list is not meant for such a use-case. Instead, consider using an Array. Array contains a set function you can use for what is conceptually an in-pace update. Here's an example:

import Html exposing (text)
import Array

type alias Model = { items : Array.Array String }

model =
  { items = Array.fromList ["a", "b", "c"]
  }

main =
  let 
    m = { model | items = Array.set 2 "z" model.items }
    z = Array.get 2 m.items
    output = case z of
      Just n -> n
      Nothing -> "Nothing"
  in
    text output -- The output will be "z"

If for some reason you need model.items to be a List, note that you can convert back and forth between Array and List.

CodePudding user response：

I'm not overly familiar with Elm, but given that it's immutable by default, I'd assume it uses structural sharing for its underlying data structures, so your concern re memory may be unfounded.

Personally I think there's nothing wrong with your approach posted above, but if you don't like it, you can try something like this (or List.concat):

List.take n list    newN :: List.drop (n 1) 

CodePudding user response：

I'm definitely not an Elm expert, but a look at Elm's List documentation did not reveal any function to update the element at a given index in a list.

I like Michael's answer. It's quite elegant. If you prefer a less-elegant, recursive approach, you can do something like the following. (Like I said, I'm not an Elm expert, but hopefully the intention of the code is clear if its not quite right. Also, I don't do any error handling.)

updateListAt :: List a -> Int -> a -> List a
updateListAt (head :: tail) 0 x = x :: tail
updateListAt (head :: tail) i x = head :: (updateListAt tail (i - 1) x)

However, both the runtime and space complexity will be O(n) in both the average and worst cases, regardless of the method used. This is a consequence of Elm's List being a single-linked list.

Regarding assoc-in, if you look at the Clojure source, you'll see that assoc-in is just recursively defined in terms of assoc. However, I think you'd have trouble typing it for arbitrary, dynamic depth in Elm.