Вопрос: Как должен быть реализован middleware?

Лучший ответ:
function app(Request $request) : Response {
    return new Response(200, "This is app response");
}

function myMiddleware(Request $request, callable $next) {
    $response = $next();
    $response->headers->add('Content-Type', 'text/html');

    return $response;
}
Это общий принцип. Декорация. Смотреть шаблон проектирования "адаптер" и "декоратор".
updated
упростим наше приложение до одной простой функции - handle, которая принимает запрос, и должна вернуть ответ. Это то как работает WEB и все вроде должно быть тут просто. Детали реализации функции нас не интересует. Внутри мы можем как-то в базу залесть, или еще чего сделать, это совершенно не важно. Нас интересуют аргумент и результат работы этой функции.
Мидлвэром же будет являться любая функция, которая будет декорировать нашу. Задача этой функции такая же как и у функции приложения. Получаем на вход запрос, возвращаем результат. Единственное отличие в том, что в качестве второго аргумента функция мидлвэр получает следующую функцию в цепочке. 
То есть если например мидлвэру нужно сделать что-то с ответом - нам нужно сначала получить этот ответ у следующей функции в цепочке, и затем уже применить свои изменения, сформировать новый ответ и т.д. В качестве примера предлагаю такой вот простенький мидлвэр:function prettyErrorsMiddleware(Request $request, callable $next) : Response
{
     // пробуем получить ответ от следующей функции в цепочке
     try {
          return $next($request); 
     } catch (Throwable $e) {
          // в случае необработанной ошибки, ловим ее
          // и формируем новый ответ с красивой версией этой ошибки
          return renderPrettyError($e);
     }
}
Имея реализацию подобного мидлвэра, мы можем реюзать его в любом проекте где требуется подобная функциональнать. Причем это удобно тестировать, это удобно комбинировать с другими "фичами" и мы всегда уверенны что получим красивое сообщение об ошибке.
Поскольку речь идет о PHP мидлвэры можно сделать объектами:class PrettyErrorsMiddleware implements RequestHandler
{
     private $errorRenderer;
     private $next;

     public function __construct(ErrorRenderer $errorRenderer, RequestHandler $next)
     {
            $this->errorRenderer = $errorRenderer;
            $this->next = $next;
     }
     public function handle(Request $request) : Response
     {
            // пробуем получить ответ от следующей функции в цепочке
            try {
                return $this->next($request); 
            } catch (Throwable $e) {
                  // в случае необработанной ошибки, ловим ее
                  // и формируем новый ответ с красивой версией этой ошибки
                  return $this->errorRenderer->render($e);
             }
      }
}
Мы так же можем прервать вызов цепочки наших функций. Например, мы можем сделать мидлвэр который занимается аутентификацией:function authentificatedEndpoint(Request $request, callable $next) : Response
{
    // если мы не передали в запросе информацию о том кто мы и что мы
    // или эта информация не является правдой
    if (!$request->headers->has('X-Authorization') || !isAuthentificated($request->headers->get('X-Authorization'))) {
         // возвращаем ошибку 
         return new Response("You are not autnentificated!", 401);
    }

    // все хорошо, можно идти дальше по цепочке.
    return $next($request);
}
Опять же, можно делать очень много реюзабельных мидлвэров, комбинировать их в разные цепочки. Или например, мы можем иметь мидлвэр, который запускает в зависимости от каких-то условий разные цепочки мидлвэров делая композицию оных.
Примерами таких вещей могут быть аутентификация, маршрутизация, CORS, логирование, кеширование, да что угодно! Вот небольшой список того что уже написано: https://github.com/oscarotero/psr7-middlewares#ava...

Худший ответ:
Пример из Redux.const middleware = store => next => action => {
  // before-action logic is above
  next(action);
  // after-action logic is below
};
Пример из Laravel.public function handle($request, Closure $next)
    {
        // before-action logic is above
        $result =  $next($request);
        // after-action logic is below
    }