Change updateAt/setAt/swapAt to return a `List a`

[cbenz]

Fixes #32

• [X] updateAt
• [X] setAt
• [x] swapAt

[witoldsz]

What do you think about leaving previous functions with maybe, eg. maybeUpdateAt? Sometimes it can be useful to get the feedback.

[cbenz]

What do you think about leaving previous functions with maybe, eg. maybeUpdateAt? Sometimes it can be useful to get the feedback.

It seems a good idea. I'd like to check if it's more convenient to use a test before, rather than checking via a Maybe afterwards.

Do you have any example code where it would be useful to get the feedback?

[witoldsz]

Do you have any example code where it would be useful to get the feedback?

No, not really. I was just thinking that someone who is using those functions already, would have easier migration path.

[cbenz]

I would prefer adding a release notes section in README.md, (or CHANGELOG.md) to explain that, rather than having non-orthogonal functions 🤔

Something like:

-- Before
list = [ 1, 2, 3 ]
updatedList = List.Extra.updateAt 42 ((+)1) list -- Nothing

-- After
list = [ 1, 2, 3 ]

-- To know if index is in list before updating
case List.Extra.getAt 42 list of
    Nothing ->
        ...
    Just _ ->
        ...

-- Do the update
updatedList = List.Extra.updateAt 42 ((+)1) list -- [ 1, 2, 3 ]

-- To know if list was updated after having updated
wasUpdated = list == updatedList

[Chadtech]

Hello, I just volunteered to be the maintainer of this repo. So I'll make sure this gets merged.

I have one point of feedback tho. I think over all, returning List a rather than Maybe (List a) is better. Returning Nothing is an imperfect way of handling the possibility that the value cannot set, updated, or swapped. That said, I do think there is a good way of handling that, thats some what independent of what this PR is about. The type signature for Dict.update is comparable -> (Maybe v -> Maybe v) -> Dict comparable v -> Dict comparable v. The Maybe v -> Maybe v part handles the case of that value not existing in the Dict. We could do something like that on our updateAt. IMO thats a good way to do it, but also I enjoy the consistency with the core Elm libraries on this point.

Let me know what you think @cbenz (and @witoldsz). I would prefer to modify the type signature of these functions just once. If my position is too disagreeable I'd be happy to just merge this PR as is.

[witoldsz]

-- Do the update updatedList = List.Extra.updateAt 42 ((+)1) list -- [ 1, 2, 3 ] -- To know if list was updated after having updated wasUpdated = list == updatedList

The list == updatedList can be slow, so I would not recommend it as a solution for a migration path. It would be much better to actually verify if the list has a 42-th element before an update.

The Maybe v -> Maybe v part handles the case of that value not existing in the Dict. We could do something like that on our updateAt.

That means you can no longer write List.Extra.updateAt 42 ((+)1) and also that you can use updateAt to actually remove the 42-th element by returning Nothing. I have no opinion if that would be convenient/inconvenient, on the other side I do remember working with Dict.update with no bad feelings about it… The consistency with the core Elm library looks like a good idea (considering the Dict.update is nice to use by others).

[cbenz]

Hi @Chadtech

Thanks for your feedback. Let's avoid changing the API too often and make propositions and good code reviews before merging :smiley:

I also like to keep consistency with the core Elm libraries, I understand your point.

The consistency with the core Elm library looks like a good idea (considering the Dict.update is nice to use by others).

A discussion I found about it was this one and doesn't seem to be problematic.

By the way the behavior of removing an item if the Maybe v -> Maybe v function returns Nothing must be documented.

---

So the proposition is, with functions signatures only:

Dict.update : comparable -> (Maybe v -> Maybe v) -> Dict comparable v -> Dict comparable v

-- Old
List.Extra.updateAt : Int -> (a -> a) -> List a -> Maybe (List a)

-- New
List.Extra.updateAt : Int -> (Maybe a -> Maybe a) -> List a -> List a

-- Usage example
updatedList = [ 1, 2, 3 ]
    |> List.Extra.updateAt 42 (Maybe.map ((+)1))

I find this solution convenient.

I'd be happy to contribute with a patch :smiley:

[Chadtech]

I'd be happy to contribute with a patch 😃

Awesome. Yeah that would be great.

[cbenz]

I modified updateIfIndex update function to be (a -> Maybe a) and deleting the item if it returns Nothing.

For updateAt, I kept the update function signature as (a -> a) to be able to express updateAt 0 ((+)1) [ 1, 2, 3 ], and not having to deal with Just << (+) 1 as mentioned in a previous comment. I think it is a good compromise :smiley:

I reimplemented setAt, removeAt and updateAt by calling updateIfIndex which makes the code smaller and more readable, I think.

I updated the documentation comments with examples, and added bunch of tests also.

It seems I can't ask for a review (the button is missing with my permissions) but I'm asking :relaxed:

[pzp1997]

I don't think updateIfIndex should be able to remove items. Honestly, it's quite counterintuitive that a function with "update" in its name, which has a connotation of simply changing a value, can be used to remove items as well. If the functionality of removing multiple items based on their index is deemed desirable, then another function called removeIfIndex should be created to handle that case.

I also question the use of indexedMap for implementing the (update|set|remove|swap)At functions. Do we really need to iterate over the entire List to perform these operations? Suppose I have a list with 10k elements and I want to remove the one at index 0, surely the approach used by List.tail would be much more efficient in this case.

[cbenz]

@pzp1997 Now I agree with you about the updateIfIndex which should not remote items. After having it under the eyes it feels strange – even if it's an adaptation of Dict.update which is in core Elm.

And indexMap should be avoided, you're right.

I pushed an update in that sense. I added removeIfIndex using indexedFoldr.

I hope there will be a consensus :)

[pzp1997]

This morning, I rewrote the (get|update|set|remove|split|swap|insert)At functions in an effort to make them more efficient. In the case of success (i.e. the index is in range), the functions perform two passes over the elements from the start of the list up to and including the given index, and in the case of failure, they require only a single pass over the list. Additionally, all of the functions are completely tail recursive.

@Chadtech Please let me know how you would like me to contribute theses changes, as they overlap with/build off of some of the changes proposed in this PR and I don't mean to compete with cbenz. Maybe I should open another PR and you can batch the two in one version update?

EDIT @cbenz I now agree with the interface (i.e. functions and their types), but not necessarily the implementations, please see above.

[Chadtech]

@pxp1997 that sounds great. What ever works for you. Can you push it to this PR?

Also, I think you are right about moving away from the Dict.update analogy. The more I thought about it the less sense it made to me. For one, unlike a Dict, Array have continuous indices. So if you get rid of an element in a Dict, the keys of the other elements arent altered, but the indices of an Array are. I also dont know what should happen if the index doest exist, and the Maybe a -> Maybe a handles it by giving a Just a. It cant just insert it beyond the length of the array.

Sorry to backtrack on this. Right now I suspect the state of this PR is good, but I would like to ruminate more on our options. We are effectively removing the functions handling of whether the index exists, and I havent really seen an argument for why. I mean, I believe that it should return List a and not Maybe (List a), but I would like a little bit more consideration. Does anyone have any further thoughts on that question? I notice the core functions Array.set doesnt return Maybe (Array a), so at least we are consistent with that. But beyond consistency, is there any explanation for this?

[pzp1997]

Okay, I ended up creating a new PR that does not change the types of the functions, so that you'll be able to consider the changes separately (we don't want to do too much in a single PR).

Regarding why we should change the types. I would say that consistency with Array is a pretty good reason. Perhaps an even stronger reason though is internal consistency. Right now, removeAt does not return a Maybe. I think for the sake of intuitiveness, it would make sense for all the At functions to return the same thing, so regardless breaking changes would need to be made.

Another strong consideration for me is simplicity in the majority of use cases. I would venture to say that most of the time, people don't care whether the index is in range or not. If they do need that distinction, then they can always implement their own solution. I think it is important to remember that the *.Extra modules don't need to provide every possible option and cover every single use case that one might ever encounter.

That being said, I could also think of compelling arguments for returning a Maybe. Perhaps we should investigate how the functions in question are most commonly used and ask for others' opinions before proceeding.

P.S. We might also want to consider stripPrefix and splitAt/splitWhen in this discussion.

[cbenz]

@pzp1997 thanks for the work! I'm gonna learn something reading your optimizations ☺️

This current pull request can wait before #55 is merged, then I'll update it to change the signatures.

I started this pull request as a user wanting the *At functions to return List a, but I'm not the only one 😊

[cbenz]

By the way does someone know a recommended way to measure performance of a function? Like a benchmark using tests perhaps?

[Chadtech]

Yeah this one @cbenz http://package.elm-lang.org/packages/BrianHicks/elm-benchmark/latest/Benchmark

[pzp1997]

I responded to the benchmarking comments in my own PR. Essentially, I decided to temporarily close the PR until we know more about the actual performance implications. I do not think that my PR should hold this one up, as it could take some time to benchmark everything and try out alternate implementations. @Chadtech what is the next step for getting this PR merged? Maybe we should ask for wider community feedback in the elm-community channel on Slack to see if people prefer returning a List a to returning a Maybe (List a)?

[Chadtech]

This looks good to me, so I think I will merge it soon.

I think some time after we merge this I'll make a PR for adding maybeUpdateAt etc, that does return the Maybe (List a).

I saw your performance PR @pzp1997. That would be great, especially if you can demonstrate the performance gain with a bench marking library.