Punishment does act as a deterrent - it just isn't as effective as we would like it to be (but I doubt it could ever achieve that). Locking people up does other things also. For a start it physically protects the rest of us from them while they are locked up contemplating their actions. It is also a means by which society can demonstrate how seriously a crime is considered. If you don't make these statements there are repercussions.

Another element is supposed to be rehabilitation...

...which is the real problem. We are absolutely crap at rehabilitation of criminals. Instead they tend to get educated and indoctrinated into a worse kind of culture while inside.