Python 3.x does have reduce, you just have to do a from functools import reduce. It also has “dict comprehensions”, which have exactly the syntax in your example.
Python 2.7 and 3.x also have a Counter class which does exactly what you want:
from collections import Counter
cnt = Counter("abracadabra")
In Python 2.6 or earlier, I’d personally use a defaultdict and do it in 2 lines:
d = defaultdict(int)
for x in xs: d[x] += 1
That’s clean, efficient, Pythonic, and much easier for most people to understand than anything involving reduce.