ENH: Handle extension arrays in algorithms.diff
Closes https://github.com/pandas-dev/pandas/issues/30889
Closes https://github.com/pandas-dev/pandas/issues/30967

This still needs a few things

1. Additional tests. It's hard to write thorough tests in `extensions/base`, since we don't know what the dtype will be after the `.diff()` (subtracting doesn't necessarily return the same dtype).
2. Decide what we want for BooleanArray.diff. Should that return an IntegerArray probably?
3. (edit) Verify that there's no perf regression for datetime, datetimetz, timedelta.

Are we comfortable doing this for 1.0.0?
Nice, thanks, this is much better as it also fixes the DataFrame case - should I close #30894 then?

Just a question about the tests: if I run
```
~/pandas$ pytest pandas/tests/extension/base/methods.py 
```
I get
```
============================================================================================== test session starts ==============================================================================================
platform linux -- Python 3.7.3, pytest-5.3.2, py-1.8.0, pluggy-0.13.0
rootdir: /home/SERILOCAL/m.gorelli/pandas, inifile: setup.cfg
plugins: forked-1.1.2, hypothesis-4.55.4, cov-2.8.1, xdist-1.30.0
collected 0 items
```

I haven't had this issue with testing before, and am able to run other tests - for example,
```
~/pandas$ pytest pandas/tests/extension/test_categorical.py 
```
collects and runs 331 items.  The tests in `extension/base` aren't meant to be run (they don't start with `Test`, so pytest ignores them). Instead, they're inherited and run for all our EAs: https://dev.pandas.io/docs/development/extending.html#testing-extension-arrays > Decide what we want for BooleanArray.diff. Should that return an IntegerArray probably?

Numpy keeps boolean dtype:

```
In [11]: np.diff(np.array([True, False, True, True]))                                                                                                                                                              
Out[11]: array([ True,  True, False])
```

(but not sure how useful it is. In any way, it is easy to switch between bool and int, if as a user you want one of both) I’ll take a closer look next week, but I think the shift & subtract implementation uses more memory than the implementation in algorithms. Didn't look very close, but I see something like this:

https://github.com/pandas-dev/pandas/blob/5d4973042f7499a79f249b578aa0d4432231ee9f/pandas/core/algorithms.py#L1893

which seems similar? > which seems similar?

Yes indeed. I thought we had our own iterative cython version, but I was mistaken.

> I am not fully convinced of the approach here.

To confirm: you're unsure of the need to add `.diff` to the EA interface, correct? You'd prefer we just implement the shift & sub in algorithms? That sounds OK to me. Hmm, one problem with BooleanArray though. We don't allow `-` between two BooleanArrays

```python
In [4]: pd.Series([True, False, True, None, True], dtype='boolean').diff()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-69fe2099d77d> in <module>
----> 1 pd.Series([True, False, True, None, True], dtype='boolean').diff()

~/sandbox/pandas/pandas/core/series.py in diff(self, periods)
   2317         dtype: float64
   2318         """
-> 2319         result = algorithms.diff(self.array, periods)
   2320         return self._constructor(result, index=self.index).__finalize__(self)
   2321

~/sandbox/pandas/pandas/core/algorithms.py in diff(arr, n, axis)
   1836
   1837     if is_extension_array_dtype(dtype):
-> 1838         return arr - arr.shift(n)
   1839
   1840     is_timedelta = False

~/sandbox/pandas/pandas/core/arrays/boolean.py in boolean_arithmetic_method(self, other)
    750
    751             with np.errstate(all="ignore"):
--> 752                 result = op(self._data, other)
    753
    754             # divmod returns a tuple

TypeError: numpy boolean subtract, the `-` operator, is not supported, use the bitwise_xor, the `^` operator, or the logical_xor function instead.
```

We do something similar with bool dtype, doing an xor instead.

```python
        elif is_bool:
            out_arr[res_indexer] = arr[res_indexer] ^ arr[lag_indexer]
```

So perhaps we check `dtype.kind` and do xor for boolean kinds. I think that's reasonable. > To confirm: you're unsure of the need to add .diff to the EA interface, correct? You'd prefer we just implement the shift & sub in algorithms? That sounds OK to me.

Yes, that would be my personal preference for now. K, doing that.

This will change the behaviore of Series[SparseArray[bool]].diff. Previously, that went to an Series[object], which is not at all usefully so I'm OK breaking / fixing that. @jorisvandenbossche can you take another look? I

1. Removed ExtensionArray.diff
2. Changed algos.diff to use the `self - self.shift(n)` for EAs
3. Changed algos.diff to use `^` for all bool dtypes (we already did it for bool / object, just added it for EAs) Will look later in more detail, but generally looks good to me > Are we comfortable doing this for 1.0.0?

I think it would be nice to include this (added the milestone), but it's certainly not crucial. 
But this PR should only alter behavior for EAs, for which it was broken before, and not for other dtypes, so it seems relatively safe to include. I'm having second thoughts about the 1.0.0 milestone. I didn't realize before, but this is a behavior change for EAs that don't implement `__sub__`. Previously, these cast to an ndarray before doing the diff, so the dtype was lost. e.g. categorical, on master

```python
In [2]: pd.Series(pd.Categorical([1, 2, 3])).diff()
Out[2]:
0    NaN
1    1.0
2    1.0
dtype: float64
```

On this branch

```python
In [2]: pd.Series(pd.Categorical([1, 2, 3])).diff()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-c632daaa2286> in <module>
----> 1 pd.Series(pd.Categorical([1, 2, 3])).diff()

~/sandbox/pandas/pandas/core/series.py in diff(self, periods)
   2283         dtype: float64
   2284         """
-> 2285         result = algorithms.diff(self.array, periods)
   2286         return self._constructor(result, index=self.index).__finalize__(self)
   2287

~/sandbox/pandas/pandas/core/algorithms.py in diff(arr, n, axis)
   1848
   1849     if is_extension_array_dtype(dtype):
-> 1850         return op(arr, arr.shift(n))
   1851
   1852     is_timedelta = False

TypeError: unsupported operand type(s) for -: 'Categorical' and 'Categorical'
```

In general, I find the new behavior more useful. Users can cast before doing the operation if that's what they want. Is this too large a change for 1.0? We could also *only* take the new path for a subset of extension types that are "safe" (eg nullable integer, for which there is otherwise a regression, and nullable integer, which is new in 1.0.0). And then we can still change the behaviour for existing dtypes later.

However, for categorical, you could also interpret it as a breaking change, which in that sense might be nice to include in 1.0 instead of 1.1. How about a middle ground. In algorithms.diff we check

```python
if is_extension_array_dtype(dtype):
    if hasattr(arr, '__sub__'):
         return arr - arr.shift(n)
    else:
        warnings.warn('losing dtype... will raise in the future..., convert before diffing...')
        # take the old path
```

that I think preserves existing behavior for people relying on the dtype being lost while letting us change the behavior in the future. That sounds good to me as well. 
It's of course possible that EAs actually have a `__sub__` but which raises an error .. (anyway, that seems a cornercase that we can ignore for now) All green.

FYI, I rewrote the base extension test a bit so that it works for boolean dtypes as well, so it's no longer skipped for BooleanArray. @TomAugspurger Thanks! @MeeseeksDev backport to 1.0.x It seems that the backports don't get automatically picked from merging PRs with the correct milestone at the moment .. Should probably check other PRs that were merged recently