Ick, that API looks ugly. For the sake of having a clean API I would stick with my current function and call keys on the way into the function, not inside of it.

That said, you must have changed more than one thing in your test run. When I run it, here is what I get:

# The test code:
print map "$_\n", find_gaps(
  qw(2000-4 2000-2 2000-1 2000-12 2001-1 2002-12 1999-12)
);
# The output
2000-3
2000-5
2000-6
2000-7
2000-8
2000-9
2000-10
2000-11
2001-2
2001-3
2001-4
2001-5
2001-6
2001-7
2001-8
2001-9
2001-10
2001-11
2001-12
2002-1
2002-2
2002-3
2002-4
2002-5
2002-6
2002-7
2002-8
2002-9
2002-10
2002-11
[download]