Spotify would have to pay artists for the right to recommend songs to users, then send those users to the artists site for purchase to be comparable.

That would be a terrible business model though. Maybe the French newspapers should join together to create a search engine of their own content, if there really is a lot of money to be made in that game.