The App Store on iPhone and iPad has been updated to include your purchase history. It's located under the "Updates" tab.
When you tap "Purchased", you will see tabs for all your purchases and ones that are not on that device. Apps that are not installed on your device have an iCloud icon with an arrow inside that will download the app when tapped. Tapping anywhere else on the app row will take you to that app in the App Store so you can learn more about it. To search for apps in either list, just pull down to review a search field.
Having access to my purchase history is a welcomed addition to the App Store. What are your thoughts on the purchase history?