They don't have to be regressive. At least here in Ontario, Canada the government cuts you a check to reimburse you for the sales tax you paid during the year (if your declared income is low enough).
In California food and any items bought with food stamps are not taxed. So the government has more or less complete freedom in reducing the regressive nature of the tax by expanding the food stamp eligibility.
In the US, you can deduct state sales tax ... but only if you don't deduct state income tax. Which somewhere like California, will usually be a much bigger deduction.