I don't write a client by doing a random walk through the API until I get to the information I need, I want to call the API that I know I need to give me the information that I want, and for performance, I want it all to be returned on a single call ideally.
e.g. If I want user B's playlist, I don't want to have to crawl:
/friends/ => ['b': { 'links': {'info': '/friends/619'} }]
/friends/619 => {'links': {'playlist': '/friends/619/playlist' } }
/friends/619/playlist
Sometimes you do a few more web calls than you might otherwise. If you can get away with it then great! Because the benefits are plenty
Hell! Even just having the uri of where the resource came from is useful enough. That's before you've introduced related resources.
The thing is, if you use well-known terms, your client will work against ANY API that uses those terms, not just the one that you coded it to work against.
Not only that, but the APIs will have flexibility to move things around, or delegate functionality to other hosts by linking through.
As for the cost of walking the chain, once a target resource has been found the can be cached, and you only need to rewalk if the resource 404/410s.
The HAL hypermedia format is in use at Comcast, powering the Xfinity TV API. Not only does it take advantage of hypermedia and HATEOAS, it also splits requests/responses in order to make the most use of HTTP caches. https://boston2016.apistrat.com/speakers/ben-greenberg
Dunno if you're serious about not seeing how one could write a HATEOAS-driven client library or if I'm being trolled, but here's one that I wrote a couple of years ago: https://github.com/gamache/hyperresource There are many others as well (especially for the HAL format).