Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add Array.Extra.splice #22

Open
gampleman opened this issue Sep 10, 2023 · 4 comments · May be fixed by #64
Open

Add Array.Extra.splice #22

gampleman opened this issue Sep 10, 2023 · 4 comments · May be fixed by #64
Labels
new function Request to add a new function to the library

Comments

@gampleman
Copy link
Collaborator

splice : Int -> Int -> Array a -> Array a -> Array a

The OG ultimate array manipulation function. Start at an index, remove a number of items and insert items in their place.

example : Array Int
example =
   Array.fromList [ 1, 2, 3, 4, 5 ]
   
splice 2 2 Array.empty example —-> Array.fromList [1, 2, 5]
splice 2 0 (Array.singleton 33)-> Array.fromList [ 1, 2, 33, 4, 5 ]

Motivating use case

  1. Porting. Since this function exists in most languages, it often comes up when porting code.
  2. various use cases that involve maintaining a sorted array as more items are added into the array
  3. Useful primitive to build other functions.

Alternative designs

a : Int -> Int -> Array a -> Array a -> ( Array a, Array a )


b : Int -> Int -> (Array a -> Array a) -> Array a -> Array a


c : Int -> Int -> List a -> Array a -> Array a

d: { start: Int, deleteCount: Int, insert: Array a } -> Array a -> Array a

a) returns the deleted items. This is rarely useful (as you can easily get the items to be deleted with a slice call) and suffers from ambiguity on which are the deleted items and which is the returned array.

b) allows the inserted items to depend on the deleted items. If you think of splice as a sort of generalised CRUD function over arrays, then this version gives you the Update. It also composes nicely with Array.map to implement a map on only a part of an array. I personally quite like this version. However, for a lot of the normal use cases it introduces a fair amount of ceremony. Also getting the deleted range is again trivial with a slice, so not particularly necessary to build it like this.

c) is a lot nicer for literal use cases. I don’t really have a way to evaluate this, but I think the type mixing is aesthetically not particularly nice. But if there was a strong argument for this, I would be willing to consider it.

d) this base signature suffers from having pairs of arguments with different meanings where the programmer just needs to know the order. This version disambiguates the call sites. I think this is somewhat mitigated in that this is a well known kind of function and the argument order tends to be like this. Also we don’t have much precedent in -extra for this style of API.

Rationale

If this didn’t exist, how would one implement this using existing functionality?

splice start delete insert array =
   Array.slice (start + delete) (Array.length array) array
     |> Array.append insert
     |> Array.append (Array.slice 0 start)

or some such. I’m not particularly confident in the correctness of this implementation and neither do I think that its intent is particularly obvious. I would also be wondering about performance and whether this is indeed a decent implementation. As such I think having it in a well tested and well performing library would be preferable.

@gampleman gampleman added the new function Request to add a new function to the library label Sep 10, 2023
@lue-bird
Copy link
Collaborator

lue-bird commented Sep 10, 2023

I like the flexibility of b a lot.

Because this helper will probably be used rarely, I'd even prefer making it more clear with something like updateSlice { start, length } changeSlice

Array.fromList [ 1, 2, 3, 4, 5 ]
    |> updateSlice { start = 2, length = 2 } Array.reverse
--> Array.fromList [ 1, 2, 4, 3, 5 ]

which still doesn't seem overly verbose in my eyes

@lue-bird
Copy link
Collaborator

lue-bird commented Sep 10, 2023

Also in your first example, are you sure it should be

Array.fromList [ 1, 2, 3, 4, 5 ]
    |> splice 2 0 (Array.singleton 33)
--> Array.fromList [ 1, 2, 33, 4, 5 ]

and not

Array.fromList [ 1, 2, 3, 4, 5 ]
    |> splice 2 0 (Array.singleton 33)
--> Array.fromList [ 1, 2, 33, 3, 4, 5 ]

@gampleman
Copy link
Collaborator Author

I like the flexibility of b a lot.

Can you clarify: would you just like to have b or would you like to have both?

Because this helper will probably be used rarely, I'd even prefer making it more clear with something like updateSlice { start, length } changeSlice

My bike shed for this was spliceUpdate. Main reason is that slice takes a pair of indices, splice takes an index and a length. I’m pretty 🤷 on verb-noun order.

We don’t have records like this in the API, but perhaps that’s a shame. Maybe we could even have multiple functions that take/return an {start, length} record.

Also in your first example, are you sure it should be

Array.fromList [ 1, 2, 3, 4, 5 ]
    |> splice 2 0 (Array.singleton 33)
--> Array.fromList [ 1, 2, 33, 4, 5 ]

and not

Array.fromList [ 1, 2, 3, 4, 5 ]
    |> splice 2 0 (Array.singleton 33)
--> Array.fromList [ 1, 2, 33, 3, 4, 5 ]

👍 that’s why doctests are a thing.

@lue-bird
Copy link
Collaborator

lue-bird commented Sep 10, 2023

Can you clarify: would you just like to have b or would you like to have both?

Good question. I was originally thinking about having only b.
Using (\_ -> new array) for replacing that slice seems quite intuitive.

The only consideration would be that the splice that doesn't take the existing, replaced section is faster since elm isn't a lazy language.

We could of course have an ugly API like

: { start : Int, length : Int } -> ((() -> Array a) -> Array a) -> Array a -> Array a

Array.fromList [ 1, 2, 3, 4, 5 ]
    |> sectionUpdate { start = 2, length = 2 }
        (\section -> Array.reverse (section ()))
--> Array.fromList [ 1, 2, 4, 3, 5 ]

But it's simpler to have one helper for update and one for replace as you described.

slice takes a pair of indices, splice takes an index and a length

I don't hate "splice" as a name for the replace version of this operation; not sure it fits the update one.
We could go for a generic "section" (or "sub") maybe?

I’m pretty 🤷 on verb-noun order.

I agree with your suggestion of putting splice/section/sub/... first :)


Another possible API could be

updateBefore : Int -> (Array a -> Array a) -> Array a -> Array a
updateFrom : Int -> (Array a -> Array a) -> Array a -> Array a

Array.fromList [ 1, 2, 3, 4, 5 ]
    |> updateFrom 2 (updateBefore 2 Array.reverse))
--> Array.fromList [ 1, 2, 4, 3, 5 ]

which is even more versatile/atomic/flexible and possibly more intuitive (since array extra already has slice from a start index and before and end index. splitAt also works quite similar)

@gampleman gampleman linked a pull request Jul 25, 2024 that will close this issue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
new function Request to add a new function to the library
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants