More Types URL structure

I came across an interesting article on WP Engineer that shows how to re-format the default WordPress search url for better readability and I was wondering how one could apply this principle to the More Types plugin?

The function they provided is:

function fb_change_search_url_rewrite() {
	if ( is_search() && ! empty( $_GET['s'] ) ) {
		wp_redirect( home_url( "/search/" ) . urlencode( get_query_var( 's' ) ) );
		exit();
	}
}
add_action( 'template_redirect', 'fb_change_search_url_rewrite' );

So, in reference to More Types, for example, I have a site where I have a custom post type of “song”. Thus the url is: /?song=song_name
It would be preferable to have it as: /song/song_name

I tried to use to use post_type_exists(‘song’) as opposed to is_search() but this resulted in an endless redirect loop and the page fails to load.

The other issue is that this would only check for a particular post type and not convert all post type urls.

What could one do in this case in order to improve the custom post type url structure?

http://ww.wp.xz.cn/extend/plugins/more-types/