apt – How to Repair Corrupt Package Installation (MySQL)

After upgrading to Ubuntu 16.04, I noticed mysql was having mind-boggling errors. Convinced, it was a broken setup, I tried running a purge of mysql. That didn't seem to delete everything, so I tried doing it myself:

sudo rm -r /etc/mysql
sudo rm -r /usr/share/mysql-workbench
sudo rm -r /usr/share/mysql
sudo rm -r /usr/share/mysql-common

This was a mistake. Don't EVER try to do this. Now mysql won't even install correctly. I've tried reinstalling the dependancies:

sudo apt-get install --reinstall $(apt-cache depends mysql-server | grep -Po 'Depends:\s+\K[^ ]+$' | tr '\n' ' ' )

And the packages themselves:

sudo apt install mysql-workbench mysql-server --reinstall

But I get all sorts of cryptic errors, such as:

sudo apt-get install --reinstall mysql-server
Reading package lists... Done
Building dependency tree       
Reading state information... Done
0 upgraded, 0 newly installed, 1 reinstalled, 0 to remove and 0 not         upgraded.
2 not fully installed or removed.
After this operation, 0 B of additional disk space will be used.
E: Internal Error, No file name for mysql-server:amd64

And uninstalling

sudo apt-get remove mysql-common
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 libmysqlclient20 : Depends: mysql-common (>= 5.5) but it is not going to be installed
 mariadb-client-core-10.0 : Depends: mariadb-common (>= 10.0.24-7) but it is not going to be installed
E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.

Or if I reconfigure

sudo dpkg --configure -a
Setting up mysql-server-5.7 (5.7.12-0ubuntu1) ...
/var/lib/dpkg/info/mysql-server-5.7.postinst: line 112: /usr/share/mysql-common/configure-symlinks: No such file or directory
dpkg: error processing package mysql-server-5.7 (--configure):
 subprocess installed post-installation script returned error exit status 1
dpkg: dependency problems prevent configuration of mysql-server:
 mysql-server depends on mysql-server-5.7; however:
  Package mysql-server-5.7 is not configured yet.

dpkg: error processing package mysql-server (--configure):
 dependency problems - leaving unconfigured
Errors were encountered while processing:
 mysql-server-5.7
 mysql-server

Or if I Force install:

sudo apt-get -f install
Reading package lists... Done
Building dependency tree       
Reading state information... Done
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
2 not fully installed or removed.
After this operation, 0 B of additional disk space will be used.
Setting up mysql-server-5.7 (5.7.12-0ubuntu1) ...
/var/lib/dpkg/info/mysql-server-5.7.postinst: line 112: /usr/share/mysql-common/configure-symlinks: No such file or directory
dpkg: error processing package mysql-server-5.7 (--configure):
 subprocess installed post-installation script returned error exit status 1
dpkg: dependency problems prevent configuration of mysql-server:
 mysql-server depends on mysql-server-5.7; however:
  Package mysql-server-5.7 is not configured yet.

dpkg: error processing package mysql-server (--configure):
 dependency problems - leaving unconfigured
No apport report written because the error message indicates its a followup error from a previous failure.
                                                                                                          Errors were encountered while processing:
 mysql-server-5.7
 mysql-server
E: Sub-process /usr/bin/dpkg returned an error code (1)

Or if I do a purge:

sudo apt-get -f purge mysql-server 
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages will be REMOVED:
  mysql-server*
0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
2 not fully installed or removed.
After this operation, 159 kB disk space will be freed.
Do you want to continue? [Y/n] y
(Reading database ... 348226 files and directories currently installed.)
Removing mysql-server (5.7.12-0ubuntu1) ...
Setting up mysql-server-5.7 (5.7.12-0ubuntu1) ...
/var/lib/dpkg/info/mysql-server-5.7.postinst: line 112: /usr/share/mysql-common/configure-symlinks: No such file or directory
dpkg: error processing package mysql-server-5.7 (--configure):
 subprocess installed post-installation script returned error exit status 1
Errors were encountered while processing:
 mysql-server-5.7
E: Sub-process /usr/bin/dpkg returned an error code (1)

Is apt unable to recover from a partial install? Do I have to reinstall the OS??