BindingResolutionException

I am attempting to register a ServiceProvider for use in a Controller, but for some reason I am encountering a BindingResolutionException. I've done some Googling and found similar questions on SO but no luck in resolving the exception.

The exact exception message I receive is:

(1/1) BindingResolutionException Target [Stockholm\Address\Domain\Handler\HandlerInterface] is not instantiable while building [App\Http\Controllers\CityController].

I define my ServiceProvider as such.

<?php

// app/Providers/AddressServiceProvider.php

namespace App\Providers;

use App\Http\Controllers\CityController;
use Illuminate\Support\ServiceProvider;
use Stockholm\Address\Domain\Handler\CityHandler;
use Stockholm\Address\Domain\Handler\HandlerInterface;

class AddressServiceProvider extends ServiceProvider
{
    protected $defer = true;

    public function register()
    {
        $this->app->when(CityController::class)
            ->needs(HandlerInterface::class)
            ->give(function() {
                return new CityHandler();
            });
    }

    public function provides()
    {
        return [
            CityHandler::class
        ];
    }
}

Register the ServiceProvider in the Providers array.

<?php

// config/app.php

return [
  'providers' => [
    // clipped
    App\Providers\AddressServiceProvider::class,
  ]
]

Define my HandlerInterface.

<?php

// stockholm/Address/Domain/Handler/HandlerInterface.php

namespace Stockholm\Address\Domain\Handler;

interface HandlerInterface
{
    // clipped
}

Define my implementation of the HandlerInterface.

<?php

// stockholm\Address\Domain\Handler\CityHandler.php

namespace Stockholm\Address\Domain\Handler;

class CityHandler implements HandlerInterface
{
    // clipped
}

Add the HandlerInterface as a Constructor argument to my CityController.

<?php

// app/Http/Controllers/CityController.php

namespace App\Http\Controllers;

use Illuminate\Http\Request;
use Stockholm\Address\Domain\Handler\HandlerInterface;

class CityController extends Controller
{
    private $handler;

    public function __construct(HandlerInterface $handler)
    {
        $this->handler = $handler;
    }
}

My PSR-4 autoload configuration in my composer.json file looks as below.

"autoload": {
    "classmap": [
        "database"
    ],
    "psr-4": {
        "App\\": "app/",
        "Stockholm\\": "stockholm/"
    }
},

via Chebli Mohamed