But slightly off the specs.

You're missing the " k = something," part of the spec :) How about?

#! perl -slw
use strict;

sub hmap(&%) {
    use vars qw[ $h ];
    my $code = shift;
    my @rv;
    local( $h, $_ ) = splice( @_, 0, 2 ), 
        push @rv, $h, $code->() 
        while @_;
    return @rv
}

sub hgrep (&%) {
    use vars qw[ $h ];
    my $code = shift;
    my @rv;
    local( $h, $_ ) = splice( @_, 0, 2 ),
        push @rv, $code->() ? ( $h, $_ ) : ()
        while @_;
    return @rv;
}

my %h = 'a' .. 'z';
print %h;

my %r = hmap{ ++$_ } %h;
print %r;

my %s = hgrep{ $h le 'm' } %r;
print %s;

__END__
[19:25:50.05] C:\test>hmap
wxefabmnstyzuvcdklqrghijop
egwyacmosuyaauwcekmgiqsoqik
egcekmacgimoik
[download]