ENH: general concat with ExtensionArrays through find_common_type
Exploring what is being discussed in https://github.com/pandas-dev/pandas/issues/22994. @TomAugspurger your idea seems to be working nicely! (it almost removes as much code than it adds (apart from tests/docs), ànd fixes the EA concat bugs ;))

Few notes compared to proposal in #22994:

- Since we already have a `find_common_type` function, decided to use this as the "get_concat_dtype", since it seems this does what is needed for concat
- Extending the EA interface with a `ExensionDtype._get_common_type` method that is used in pandas' `find_common_type` function to dispatch the logic to the extension type

What I already handled:

- general protocol, using this for concat with axis=0 (eg concatting series) and using it as example for IntegerDtype
- handling categoricals this way (which removes the `concat_categorical` helper). This turned up a few cases where we have value-dependent behaviour right now, which we can't easily preserve (mainly regarding NaNs and int dtype, see below)

Still need to handle sparse (those has failing tests now) and maybe datetime, and check other failures.
I needed to make one change to the tests related to categorical (another value-dependent behaviour). Assume those examples involving integer categorical and float arrays:

```
In [13]: pd.concat([pd.Series([1, None], dtype="category"), pd.Series([3.5, 4.5])])    
Out[13]: 
0      1
1    NaN
0    3.5
1    4.5
dtype: object

In [14]: pd.concat([pd.Series([1, 2], dtype="category"), pd.Series([3.5, 4.5])])    
Out[14]: 
0    1.0
1    2.0
0    3.5
1    4.5
dtype: float64
```

With a `find_common_type`, we will always find float. But the old behaviour is that the integer categorical becomes object if there are missing values present. 
But I would say: if you are concatting with a float anyway, it doesn't make sense to try to provide the "integer categories" by keeping it object instead of casting to float.

So I would say that the new behaviour (always returning float in the above two examples) is better.
 I ran into one other hairy question:

- Should `_get_common_type` be able to handle "not fuly initialized" dtype objects? Like a CategoricalDtype without categories? (which we have to handle "category" string).  
  And if so, what is the expected behaviour?


Right now I added some special cases in `Categorical._get_common_type` to have the find_common_type tests passing, but not sure it is necessarily doing the correct thing in a general way.
 I like this idea, will want to give it another look after more caffeine.  Haven't looked at the tests or Categorical-specific nuances yet. > [@jreback] why is this a private method on the Dtype? get_common_type (or get_common_dtype) seems fine

This was briefly touched upon in https://github.com/pandas-dev/pandas/issues/22994#issuecomment-614249196. The reason to make this private, is because the method is not meant to be used by *end users*, but only meant to be implemented by *EA authors*. And thus, we think that a private method is appropriate here (similarly as `EDtype._is_boolean/_is_numeric`, `EA._from_sequence`, `EA._concat_same_type`, ... are also all private methods to the user, but part of the public EA interface).

But what actually might be useful to publicly expose (eg in `pd.api.types`) is the `find_common_type` function (which this `_get_common_type` is helping implement). I can image this could be useful for eg dask? (@TomAugspurger ?) A public `find_common_type` might be useful, but don't let Dask be the motivator. We would get the result dtypes by doing an actual concat on two empty DataFrames. More comments here?

Note I added some questions regarding the `ExtensionDtype._get_comon_type` interface at the base implementation:

- do we guarantee that `dtypes` is already deduplicated? (passing a list of unique dtypes)
- do we call this method if `len(dtypes) == 1`, or should this method need to handle that case?
- does this method need to handle "non-fully-initialized" dtypes? (for concat, you will never run into this, since the dtypes are always coming from actual arrays) > do we guarantee that dtypes is already deduplicated? (passing a list of unique dtypes)

Currently I didn't do this yet in `find_common_type`, but probably should. 
@TomAugspurger you wrote this part in your pseudo-code in the issue as `{x.dtype for x in arrays}`, but I don't think that sets preserve order? (which we want here, possible workaround seems to be `dict.fromkeys`, this has much less overhead as pd.unique) I don't thin sets are required to preserve order.

You could maintain a mapping like (pseducode)

```python
seen = set()
uniques = {x.dtype for x in arrays}
for array in arrays:
    if array.dtype not in seen:
        common_dtype = array.dtype._get_common_type(uniques)
    seen.add(array.dtype)
    if common_dtype:
        break
```

Will try to look again in a bit, but don't wait up for me. API Questions:

- Should `_get_common_type` be a classmethod?
- Are we implicitly assuming that `self.dtype` is a member of `dtypes`?
    - If so, can we make that explicit
- In the case (mentioned in a comment on the base class) where `dtypes` is a singleton, can we require that the return value be that dtype?
- Can we nail down the common_type vs common_dtype semantics before pushing this through?  I feel like that has been a major cause of trouble with the existing concat code. > Are we implicitly assuming that `self.dtype` is a member of `dtypes`? 

Right now, this is the case yes. What do you mean with making that explicit? (just better documenting it?)

> Should `_get_common_type` be a classmethod?

It could be, but personally I don't really see to not make it an instance method. Yes, `self` will always be in the list of `dtypes` (see question above), but I can assume that for the implementation it can be useful to know self (instead of needing to infer it from the list of dtypes). Not that this should impact the *result*, I only think it can be handy in the implementation (but this is rather hypothetical feeling at the moment). 
The main thing is: we always call this from the instance, so I don't see much value in making it a class method instead of instance method.

> In the case (mentioned in a comment on the base class) where `dtypes` is a singleton, can we require that the return value be that dtype?

This is the only sensible return value in such a case (an EA doing anything different will behave very strange). But what do you mean with "require"? Better document it? Or we could have a base extension test that asserts it? 

But see also my question above (https://github.com/pandas-dev/pandas/pull/33607#issuecomment-617403497): in principle we don't even need to call this `_get_common_type` method if there is only one dtype in the list. In the concat code / `find_common_type` code, we can simply use this dtype and shortcut calling `_get_common_type`.

> Can we nail down the common_type vs common_dtype semantics before pushing this through? I feel like that has been a major cause of trouble with the existing concat code.

Can you explain this a bit more? I am not aware of any troubles regarding that. I have also been reading up on numpy dtype proposals regarding this. Specifically this part of the draft NEP relates to "common dtypes": https://github.com/numpy/numpy/blob/f07e25cdff3967a19c4cc45c6e1a94a38f53cee3/doc/neps/nep-0042-new-dtypes.rst#common-dtype-operations

It's actually quite similar in idea, but some notable differences:

- The dtype special method is limited to a *single* other dtype (they have `Dtype.__common_dtype__(self, other)` where `other` is a single dtype), instead of passing the list of all dtypes
- They split the "common dtype" special method in two: determine the common *class* (from 2 different dtype classes), and determine the common *instance* (from 2 instances of the *same* class). And it is actually split in 3, because those 2 steps are then combined with as cast-lookup.

The first is an interesting idea. The second might only complicate it more for *current* pandas (although I understand its desire to split it up on steps to avoid duplicate logic in different parts). 
And I also don't know if first doing it on the *class* level will work for pandas' current promotion logic. Eg the common dtype of Categorical + int dtype depends on the dtype of the categories of the Categorical.

 >> Can we nail down the common_type vs common_dtype semantics before pushing this through? I feel like that has been a major cause of trouble with the existing concat code.

> Can you explain this a bit more? I am not aware of any troubles regarding that.

"trouble" in that we haven't been consistent about where some logic belongs.  e.g. DTA._concat_same_type requires a single dtype, not just same-type. With this PR, `EA._concat_same_type` will only be called with arrays of all the same dtype. 
(and which needs to be better documented now, as that was not clear from its docstring what the expectations were before)

Does that answer your concern? Otherwise you will still need to clarify further what you mean.
 > Does that answer your concern? Otherwise you will still need to clarify further what you mean.

Close enough. I made a bunch of updates (renamed to use "dtype" instead of "type", documented the public API change and updated the EA interface docs, added a base extension test). 
Ready for another review (or approval ;)) round thanks @jorisvandenbossche very nice And thanks all for the review!