Ohhh, this is delightful! I’m still digesting the implications, but it does model it beautifully. When I get time to fiddle I’ll see whether this could work nicely with QualifiedDo! Thank you!
Also curious about whether this would need and/or be amenable to a set of useful combinators similar to those usually available for regular monads/applicatives. There’s not much on Hackage about relative monads. Fertile ground for budding library authors? 
Also, why does the Action type use both free monads and free applicatives? Wouldn’t just using Free be equivalent in power?
By convenience. The free’s Ap gives you a Functor instance for any f that doesn’t have one (my GADT Spec type doesn’t), and free’s Free wants something that’s an instance of Functor. I suppose a freer monad would do the same trick that Ap is doing for me. But I think overall these are implementation details.
You could use kan-extensions:Data.Functor.Coyoneda.Coyoneda for that if you don’t need the intermediate free Applicative, at which point you’ve hit on the same type as the one that shows up in @ocharles 's providing an API for extensible effects and monad transformers:
class Monad m => MonadListenBrainz m where
liftListenBrainz :: Free (Coyoneda ListenBrainzAPICall) a -> m a
Oh, good pointer! Yeah, it could be exactly that. I’ll update the blog post.
It’s not particularly important for the thrust of the post. But it’s a nice refinement of the example.
@emekoi would you be able to provide your name? I’d like to mention on my blog post the connection to relative monads and who pointed it out to me.
Sure, my name is Emeka Nkurumeh.