To all those claiming it can't be uninstalled, note that the poster said they were using a dev phone. Using dev utilities, most things can be uninstalled.
There is no Cortana download in the store I believe (even hidden), as it is never updated through the store but through Windows Update instead, so the only way to reinstall is a hard reset.