iOS: Photos app taking 800 MB after deleting all photos
Check under Photos' Recently Deleted album. From the Albums view, it appears as a trash can.

Since iOS 8, photos that have been deleted remain on your phone under the Recently Deleted album and are automatically deleted after 30 days, or until you delete them yourself, after which they are permanently gone.

The images in this album still occupy space on your phone. To remove them, go into the album, tap "Select" in the top right corner, and then "Delete All" in the bottom left corner.