Untested, but I often get this stuff right on the first try... :)

my $words = { 
   'lng'       => ['lang', 'long', 'leng', 'loo'], 
   'sentance'  => ['sentence'], 
   'thxs'      => ['this', 'thus'] 
};
print map "$_\n", phol($words);
sub phol {
  my($key, $value, @rest) = %{+shift};
  if (@rest) {
    return map { my $r = $_; map { "$_ $r" } @$value } phol({@rest});
  } else {
    return @$value;
  }
}
[download]

-- Randal L. Schwartz, Perl hacker