First of all I would like to mention that defining callbacks with the @callback directive is discouraged.
While it can still be used, ExDoc will not list these callbacks in the protocol documentation.
See this issue for reference.

The approach that I ended up taking was to define a submodule called Behaviour, where you can end up placing all your @callbacks. There is a caveat though, that the functions that define functions/macros are not available, this is due to the way protocol is implementing disabling these functions in the parent module. One way to solve this is to create a module outside the protocol definition (defmodule MyProtocol.Behaviour).
But for clarity I preferred to keep it as a submodule.
You can see the implementaiton of this here:

Please let me know what you think about this approach

It seems to me like we are treading in unexplored waters, and am eager to learn what people of the Elixir core have to say about this situation.

Let me give some extra context. There definitely are situations in which I’d go for @LostKobrakai 's approach, but it cannot be used here.

Arrays and some similar libraries (e.g. okasaki, sets, prioqueue) have a unified interface module (in this case Arrays) which contains some generic code. For some functions this generic code calls a particular protocol implementation.

This pattern is common elsewhere in Elixir. For instance we have an Enum module which contains generic code that internally uses the Enumerable protocol implementations.

The idea is that user code should (only) use the unified interface, and that they can specify in configuration (either in config.exs or by passing explicit options to Arrays.empty/1 or Arrays.new/2) which array implementation they want to use.

This works great, except when actually creating the initial structs (. Here we cannot dispatch to the protocol implementation because we do not have a struct yet. We only have the module name.
And that is where the conundrum lies.
What do we do for this situation?

Adding a function (also called empty) to the module that contains the defstruct as @al2o3cr is indeed the current approach.
To make it slightly more clear that we need this module to implement this particular function we use a behaviour.

However, this means we have ánd a behaviour ánd a protocol, with the pros and cons outlined in the first post above.
We’re looking for ways to make the interface of the library as a whole better.
(For both users as well as implementers of new e.g. array backends).

ˋArraysˋ is not the protocol though – ˋArrays.Protocolˋ is. Your public API is not your protocol, and given the constraint you mentioned it cannot be. Same for e.g. ˋEnumˋ btw. The protocol is ˋEnumerableˋ while ˋEnumˋ uses it to provide a nice API. But on the other hand take a look at ˋAccessˋ, which is actually a behaviour (even when often mentioned to be a protocol), which you need to implement to have datatypes be accessible as data containers.

You‘re obviously in a situation where you need both the behaviour version of datatypes providing certain functions as well as the protocol side. What I suggested would at least remove the need of explicitly defining the protocol implementation unless something truly custom needs to happen. The downside to behaviours however is that they cannot be implemented in userland like protocols can.

In the end I question if you actually need ˋemptyˋ on the protocol, because how useful is ˋArray.Protocol.empty(…)ˋ if there‘s nothing to dispatch on. For ˋEnumˋ one would also do ˋMapSet.new(list) |> Enum.map(…)ˋ as well.

Protocol already defines a behaviour, so you should just declare that behaviour in an outer module that defdelegates to the protocol module.

If you do the following, you will see that dialyxir/elixir_ls indicates the error “type mysmatch for @callback f/1 in P behaviour”

defprotocol P do
  @spec f(term) :: atom()
  def f(x)
end

defmodule I do
  defstruct []
  defimpl P do
    def f(_x), do: 32
  end
end

defmodule Pr do
  @behaviour P

  defdelegate f(x), to: P
end

moreover, if you do Code.Typespec.fetch_callbacks(P) it will show you the correct callback for the P.f/1 function.

I also just verified that you can add extra callbacks to the Protocol callback if you desire.