Compute the most efficient binary function Today, we'll be computing the most efficient binary function. More specifically, we'll be computing the function which, when an expression is created from applying the function to the constant input 0 or its own output, can represent all positive integers with the shortest possible expressions, placing higher priority on the smaller integers.

This function is built as follows:

For each integer, starting at 1 and going upwards, choose the shortest expression which we have not yet assigned an output to, and make that integer the output of that expression. Ties in expression length will be broken by smaller left argument, and then by smaller right argument. Here's how it works:


Initially, 1 is unassigned. The shortest unassigned expression is f(0, 0), so we'll set that to 1. 
Now, 2 is unassigned. The shortest unassigned expressions are f(f(0, 0), 0) = f(1, 0) and f(0, f(0, 0)) = f(0, 1). Ties are broken towards smaller left argument, so f(0, 1) = 2.
The shortest unassigned expression remaining is f(f(0, 0), 0) = f(1, 0), so f(1, 0) = 3.
Now, we're  out of expressions with only 2fs and 30s, so we'll have to add one more of each. Breaking ties by left argument, then right argument, we get f(0, 2) = 4, since f(0, f(0, f(0, 0))) = f(0, f(0, 1)) = f(0, 2).
Continuing, we have f(0, 3) = 5, f(1, 1) = 6, f(2, 0) = 7, f(3, 0) = 8, f(0, 4) = 9, ...


Here's a table I filled out for the first few values:

    0  1  2  3  4  5  6  7  8
 /---------------------------
0|  1  2  4  5  9 10 11 12 13
1|  3  6 14 15 37 38 39 40 41
2|  7 16 42 43
3|  8 17 44 45
4| 18 46
5| 19 47
6| 20 48
7| 21 49
8| 22 50


Another way to look at it is that each output has a size, equal to the sum of the sizes of its inputs plus one. The table is filled out in order of increasing size of output, ties broken by minimizing left input then right input.

Your challenge is, given two non-negative integers as input, compute and output the value of this function. This is code golf. Shortest solution, in bytes, wins. Standard loopholes are banned.
Haskell, 110 bytes

f q=head[i|let c=[(-1,0)]:[[(f a,f b)|n&lt;-[0..k],a&lt;-c!!n,b&lt;-c!!(k-n)]|k&lt;-[0..]],(p,i)&lt;-zip(concat c)[0..],p==q]


The argument here is taken to be the tuple (x,y). Pretty similar to the answer above, but the lookup list holds just the pairs of left and right indices instead of the trees.