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