Each item in the list is going to have a URI for the item, probably some text that briefly describes the item, and if necessary it can have a value that identifies the type of item.
If I'm understanding correctly, your playlist resource is an ordered list of song identifiers, the song identifiers can appear more than once, and when you "delete a song" you're removing a single one of those identifiers. That sounds to me like an update of the playlist resource. The simplest model would be:
GET /playlist/{playlist id} ... client modifies representation ... PUT /playlist/{playlist id}
That's not atomic and it puts some application-logic burden on the client, but you _are_ writing an API to allow others to develop full-featured clients, and maybe the burden also provides flexibility for operations you haven't thought of.
Another approach would be for the representation of the playlist to include a unique id for each item in the list: your song id + index. You're not using a DELETE method here though, because you're not deleting a resource. You would use POST to update the playlist resource:
POST /playlist/{playlist id} operation=removeitem&songid={song id}&index={index}
This is the general RESTful pattern for doing a partial update of a resource, so the client doesn't have to GET and PUT the complete resource.
Your opinion is a fact, imo. Songs can't be deleted from playlists using REST, full stop. Songs-in-playlists are values, not identities, so they can't be resources. I see it as analogue to words in a text file. A REST client would have to construct the updated playlist value and PUT the whole thing to the playlist resource. So "delete song from playlist" is a function that could only exist in the client.
Search on the other hand is just search. I don't think REST vs RPC has much to say about it. The only issue would be location: URL vs method.
This doesn't parse very well to me.
As far as your main point, I disagree. The /playlist/:playlist_id/:song_id/:index thing doesn't seem very good, no. But, if you kept an id that mapped songs to playlists, you could easily do DELETE /playlists/:playlist_id/:song_playlist_id and be done with it.
REST doesn't say you have to update the entire resource just because a member of that resource needs to be deleted.
They could, in theory, have ids for songs-in-playlists. But they don't in fact have them and their RPC api doesn't require them. That's what I'm interested in. Not how they could change their architecture to make REST work.
I'm not certain DELETE is completely inappropriate here[1], but if you feel strongly about it, probably the best/REST way to “delete” a song from a playlist would be to PUT the playlist without the song included.
[1] It is just an ordered list of songs, after all.
In short: you want to offer functions on the server that REST would push on to the client (or would require making architectural changes).
REST definitely requires a larger upfront investment vs RPC. Part of what I'm curious about is how much larger in real world cases, and this is a good example. So I appreciate you taking the time to respond.
As far as deleting songs "safely", what Ian means is that for any given playlist (of which a user has an unlimited number) any given song can be in it any number of times. So when you delete a song, we generally ask for song_id and index to make sure that a) the playlist hasn't mutated (much), and b) we are dropping the right song. The DELETE on /{trashbin uri}/{song id} doesn't provide 2 of the 3 required bits of information, and DELETE /playlist/{playlist id}/{song id}/{index} isn't very RESTful (imo).