WIP: categoricals as an internal CategoricalBlock GH5313
This PR creates a `CategoricalBlock` as a first class internal object, on par with blocks like `Datetime,Timedelta,Object,Numeric` etc.

closes #5313
closes #5314
closes #3943

TODOS
- [x]  test with `select_dtypes` #7434, https://github.com/jreback/pandas/commit/a43c6c041c7870c63992bc15b427adc35f7ab5d8

**Code Changes**
- [x] `factor_agg/group_agg` in `core/frame.py` -> look at unittests // a google search didn't turn up any questions/usage -> remove them?
- [x] Add a API change note about the group_agg and factor_agg
- [x] Add a API change note about Categorical.labels -> Categorical.codes
- [x] Printing level information when a Series of type categorical is printed?
- [x] Fix the remaining "FIXME" in tests 
  - [x] Groupby -> include each level, even if group is empty
  - [x] Pivotable -> include each level, even if group is empty
  - [x] `Series(categorical).describe()` / `Categorical.unique()` -> should this return all levels or only used levels?
  - [x] Series(cat).describe() -> show information about the levels?
  - [x] sort by index?
  - [x] df.to_csv: fails due to a slicer error?
  - [x] concat/append -> should retain categoricals
  - [x] concat/append -> should raise on different levels
  - [x] sorting a dataframe by a categorical variable does not use the level ordering
  - [x] sorting by a unsortable categorical should not be possible and should raise
  - [x] reorder_levels: raise if set(old_levels) != set(new_levels)?
  - [x] min/max and numeric_only=True
  - [x] df.to_hdf: fails due to `categorical.T` not implemented
  - [x] `Category.describe()` with empty levels (will be fixed with groupby)
- [x] TST: apply -> look into it if/how it works -> should probably convert first and don't try to preserve the categorical
- [x] TST: def test_sort_dataframe(self): -> sort df, cats must also be sorted!
- [x] TST: Add tests about some more numpy function that should fail
- [x] labels vs. pointers: should the (internal) name of integer array be renamed? -> I would like to see a rename to something with a underscore and it would be nice to rename it to another name (`_pointers`, `_level_idx`, `_level_pointer`)

**Documentation**
- [x] Add release notes
- [x] Add a API change note about the old constructor mode
- [x] Document the Categorical methods
- [x] Link classes/methods in categorical.rst -> not done, just a link to API docs and in special cases.
- [x] Add Categorical API to API docs

**Future**
- [ ] HDF support? -> see above... #7621 
- [ ] meta infos / "Contrasts": R's factor has a "contrast" property which indicates how this factor should be used in statistical models -> don't do it in the PR

cc @immerrr 
 @jseabold feel free to jump in here for commentary 
 @jreback See https://github.com/JanSchulz/pandas/tree/categorical_improvements
- new way to build a Categorical: `Categorical(["a","b"], levels=["b","a"])` 
- "ordered" keyword 
  - implement sort/min/max in Categorical
  - sort in `Series(Categorical(...))`

What doesn't work yet:
- min/max doesn't yet work as a `Series(Categorical(...))` -> not sure yet what I have to implement to get this working
- labels
- assigning new levels (needs some reorderung,...)
- performance improvements?
 ok will have a look

why did you change labels -> _values_pointer
that is not common nomenclature afaict

on the surface this seems to break back compat is that true?
 The problem with the "old" labels was that they were "pointers" and labels in R have a different meaning:

R: labels are other names for levels
old pd.Categorical: labels are pointer to levels

pseudo code for future label usage, which is IMO compatible with R

```
a = Categorical([1,2,3,1], levels=[1,2,3])
a.labels = ["x","y","z"]
a.__array__() == ["x","y","z","y"]
a.labels = ["low","medium","high"]
a.__array__() == ["low","medium","high","low"]
```
 One question: how do one get to the underlying data structure from Series?

`s = Series(Categorical(...))` -> how do I get the levels/labels from `s`

That would be the most interesting feature from ggplots side: we want to get the levels/labels from the dataframe which is passed to the plotting functions
 ok so labels are descriptors of the levels (if provided)
and value_pointers are what we call labels now

hmm

what if we call values_pointers:

locs or index?
 Series(Categorical(....)).values returns the Categorical itself
 however we could define labels/levels as a property on Series that only works on categorical series (I think), or a method if u need to pass in arguments
 I don't mind the names, I just think the "pointers" are an internal implementation detail and shouldn't show up in tab completion. 
 I'm off to bed, will be back tomorrow evening...
 @JanSchulz do you have any idea where/what purpose of `factor_agg/group_agg` in `core/frame.py` are for?  I don't see them used anywhere but in a couple of tests. Maybe existed  before the groupby code handled Categoricals (which is what this looks like its doing). or am I missing something?
 @JanSchulz 

ok I have a new version which incorporates your changes
- delegates reductions ops from Series to the Categorical itself (so these end up alling the min/max you defined)
- other reduction ops raise TypeError (var,mean,sum) etc
- numeric ops raise TypeError (e.g .`cat1 + cat2`)
- sorting was off a bit; its now works on copies and `sort` is inplace, and `order` returns a copy (just like Series)
- I changed `_value_pointer` back to `labels` for consistency with the rest of the library. I know you don't like it, but its 'internal' anyhow.

what's still missing?
 After a bit more poking at Rs factors, I think labels there are kind of waste of time: I think changing levels in R will do renaming/reducing/appending of levels. It seems labels are simple there to change the names of the levels in one go during creation of a factor, but that can also be done afterwards with changing the levels. So I'm fine with that change back from pointers to labels, although I still find it strange, as from my (German, so non-English) POV labels are "names for something", so actually I would have expected the other end to be the labels ("pointers point to labels").

in R, a categorical is always strings (so the first thing would be to convert values to strings), but I think we can miss that.

Anyway, I think the main part missing is a API which reorders/reduces/expand levels based on an input array/list and renaming of levels:

```
c = Series(Categorical([1,2,3,4,1], levels=[1,2,3,4])
# all following examples would operate on this one...
c.labels == [0,1,2,3,0]
c.levels = [1,2,3,4] 
c.get_values() == [1,2,3,4,1] 
# reorder would basically replace the levels and do a replace on the pointers/labels so that they point to the same 'levels' (or in my speak 'labels')
c.reorder([4,3,2,1]) # all "pointers" to '4' must be changed from 3 to 0,...
c.labels == [3,2,1,0,3] # positions are changed
c.levels == [4,3,2,1] # levels are now in new order
c.get_values() == [1,2,3,4,1] # output is the same
c.min() == 4
c.max() = 1
# assigning to levels would simple exchange the levels array
c.levels = [4,3,2,1] 
c.labels == [0,1,2,3,0]
c.levels == [4,3,2,1] 
c.get_values() == [4,3,2,1,4] 
c.min() == 4
c.max() = 1
# assigning a longer array will add a level 
c.levels = [4,3,2,1,0] 
c.labels == [0,1,2,3,0]
c.levels == [4,3,2,1,0] 
c.get_values() == [4,3,2,1,4] 
c.min() == 4
c.max() = 0
c.levels = [4,3,"a",2,1] 
c.labels == [0,1,2,3,0]
c.levels == [4,3,"a",2,1] 
c.get_values() == [4,3,"a",2,4] 
# assigning a shorter array will make that values NA
c.levels = [4,3,2] 
c.labels == [0,1,2,NA,0]
c.levels == [4,3,2] 
c.get_values() == [4,3,2,NA,4] 
# assigning a NA level could do two things: make that value NA or the level would be NA
# I would vote for the latter, as otherwise we would need to check each new level for NAs...
c.levels = [4,3,2, NA] 
c.labels == [0,1,2,3,0]
c.levels == [4,3,2, NA] 
c.get_values() == [4,3,2,NA,4] 
```

I also think that operations based on categorical levels (groupby, etc) should return groups for all levels and not only the ones, which have values -> empty groups for levels without values.
 Note: I am not really following this, or a user of categorical types at the moment.

But, seeing this PR and the discussion, and as this is a really big and important new feature and addition to the pandas 'language' (not just a new method/function), I was wondering if it would be better to first lay-out the design (API, naming, ...) in a kind of 'design document' (something like a PEP for pandas)?

Just from a brief look,  it seems there is still some discussion about the naming of things, how certain operations should work exactly, ... This is also something that should be discussed broader I think (with more people who would use this, send it out to the list), but it is now difficult to engage in the discussion with only the code to look at and the discussion in this PR.

Having an overview with the reasoning behind this new type, the naming, the API, how you create it, how to do common operations on it, how it behaves in other pandas methods, some examples of applications, (maybe a short comparison with R), ... could be beneficial for making this a more solid enhancement, but also to facilitate the dicussion (and afterwards this can be used as a start for some documentation, so certainly not 'wasted' in that regard).

Just a remark from the sideline. What do you think? 
@JanSchulz Would you be able to start something like that?
 I think someone from the statistics side should comment on this: cc @jseabold @josef-pkt and @cancan101 @kshedden @upandacross @cfarmer because they had some issues open which showed up after a search for "categorical" in Statsmodels

I come from ggplot and plotting and I'm actually after the "reorder bar charts" (-> reorder levels)and "make faceting easier by letting empty levels show up in groupby" feature (see linked issues above).

I can do a comparison with R: creation, adding to a df, reorder levels, change levels, groupby. Something else?
 What also needs to be tested is "add to a df, sort the df on another column, see that the categorical series is changed accordingly". Also selection: `df[df["cat_col"] == 4]` should select the right rows
 @JanSchulz I think what @jorisvandenbossche is looking for is essentially the documentation for how to work with Categoricals. Categorical DO exist now, so in reality this PR is just making them a first class object, but adding abilities that weren't possible before. We have lots of functionaility (and some todos). Most of this already exists in the tests. Just really need an extended example with commentary that can turn into docs directly. So pretend I am reading the doc sections, and come across *Working with Categorical``. 
- So, I want to start with some data
- convert to Categoricals (`cut`); and use the constructor directly.
- put in a DataFrame (with some other data).
- order / select values (direct selection, `min/max`)
- setting (this is really tricky; most pandas operations return copies so have to be very very careful about mutability here)
- grouping

The main question I have is, you have created a Categorical, what/how/when do you use it?
 Pinging @njsmith in case he also wants to comment. I never use R's factors.
 I kind of agree with @jorisvandenbossche.

Categoricals may well exist as of now, but they felt like sort of "there-be-dragons" feature to me, like you must know what you do around them. That's not always bad, because it means there's no guarantee for backward compatibility and thus your hands are untied if you see something _really_ wrong with the API.  If we are to "legalize" them letting them into the "public" section of the API, this will severely limit the future opportunities to make amends if any of the tentative decisions prove wrong.

Hence I'd suggest the design decisions to be laid out in plain sight to be examined by anyone interested. Actual code and comments are less useful in this regard because it's not always clear if this or that was intended or was it just never considered. Examples/cookbooks are better but add some rationales and you've got yourself an almost proper PEP (see https://github.com/cython/cython/wiki/enhancements for example).

I'd also love the first versions of the soon-to-be-public API to "boil" in experimental mode for a while to be able to play with them and see if the decisions work out without hasting to make it before 0.14.1.
 FWIW, my use case for these (so far) is almost always just to call `.describe()` on them and have it give me some sensible descriptive statistics. Beyond that, just being able to hand off a DataFrame that contains one to a statistical model and have it be recognized as a Categorical will be nice. Patsy does some of this already (for string/object types), but if you don't go through the formula api of statsmodels there's no easy way to do this. It will also be a nice feature to be able to associate a particular contrast with a categorical variable. So some kind of container for meta-data or attribute might be appropriate here.

http://stat.ethz.ch/R-manual/R-patched/library/stats/html/zC.html

+1 for a PEP and more mailing list/community discussion.
 all good points here! I guess this change was to KEEP the same API, so will move to 0.15.0 pending further discussions.
 @jreback maybe some docs are indeed enough for what I was looking for, as I was not fully aware that the Categorical already existed (I just thought it was some experimental feature that was not further developed, as there is exactly zero documentation about this).

On the other hand, if we want to make some changes to the API, it is now the moment when making it a first class citizen and adding documentation.

It was also because I saw quite some discussion about the API (naming for levels/labels/values/pointers/..., how they should behave in certain operations, .. in the discussion in this PR and #6242), that I thought this should require a broader discussion.
 @JanSchulz you want to put out an e-mail (and hit numpy-discussion) as well to summarize / probe for thoughts?
 Please, oh please, don't break the API without a really good reason / without deprecation. I do use `pd.cut` and Categoricals quite a bit in my code.
 @jseabold actually this PR does NOT change the API in any way, that was the point.

just makes `Categorical` a first-class object (e.g. currently its basically converted to an `object` array) not very useful.
 Sure. Just responding to comments that it's ok to break API for 0.15.0.
 From patsy's point of view:
- Better categorical support would be great.
- If it would be possible to attach metadata to a specific categorical "dtype object" that is automatically propagated along with levels etc. then that would be super super helpful. Specifically my use case here is that people want to specify how a given set of levels should be encoded when used in a statistical model, so the information should be "attached" to the levels: see the examples involving `Poly` and `ContrastMatrix` here: http://patsy.readthedocs.org/en/latest/categorical-coding.html
- I think "labels" is a terribly confusing name for the underlying integers, please don't use this :-(. Even "level_int" or "level_idx" or something would be better.
 @njsmith can you give a concrete example of what you mean by attaching metadata?
 This syntax is certainly terrible in a number of ways, but this kind of
functionality:

a = Categorical(["a1", "a2", "a1"], contrast="whatever")
assert a.contrast == "whatever"
partial_a = a[:-1]
assert partial_a.contrast == "whatever"
partial_a.contrast = "something else"
assert partial_a.contrast == "something else"
assert a.contrast == "whatever"

If this were pure numpy, then the categorical levels would be encoded into
a special parametrized dtype object, and in that case I'd attach the
metadata to the dtype object:

a = np.asarray(["a1", "a2", "a1"], dtype=CategoricalDtype(levels=["a1",
"a2"]))
a.dtype.contrast = "whatever"

I'm not sure what the equivalent would be in the pandas view of the world.

I don't know if it would be better to have a generic metadata system that
allows arbitrary attributes, or just a special case for "contrast" --
"contrast" is the only attribute that patsy cares about, and I don't know
if there are any others that matter to anyone else.

I don't care if the syntax to read/write this kind of metadata is slightly
convoluted, a.metadata["contrast"] or whatever instead of a.contrast.

-n

On Wed, Jun 4, 2014 at 3:04 PM, jreback notifications@github.com wrote:

> @njsmith https://github.com/njsmith can you give a concrete example of
> what you mean by attaching metadata?
> 
> —
> Reply to this email directly or view it on GitHub
> https://github.com/pydata/pandas/pull/7217#issuecomment-45094249.

## 

Nathaniel J. Smith
Postdoctoral researcher - Informatics - University of Edinburgh
http://vorpus.org
