Induction is your friend when looking for solutions to this kind of problem.
For the easy case, it looks like
easy( a, i ) ≡ easyHelper( a, a.length, i )
easyHelper( a, n, i ) ≡ easyInduction( easyHelper, 0 )( a, n, i )
easyInduction( f, b )( a, 0, 0 ) ≡ []
easyInduction( f, b )( a, 0, i + 1 ) ≡ undefined
easyInduction( f, b )( a, n + 1, i ) ≡
let t = a[n + 1].length - b
in f( a, n, ⌊i / t⌋ ) ++ [ a[n + 1][i mod t] ]
For the hard case, I think you need a stronger inductive assumption. That is, your helper recursive method needs to return both an offset and a function mapping specificities to tuples. The function, when applied to indices below the offset, returns the member of the cross product of all the arrays with the nulls removed; above the offset the null cases start. Knowing this for the case of n arrays, you can construct the new offset and the new function for n + 1 arrays, via the following three cases:
- you're less than the new offset, so you treat it like the easy case for the non-null members of the last array
- you're between the new offset and the sum of the new and old offsets, so you should return the recursive result with a null on the end
- you're bigger than the sum, so you again treat it like the easy case, except you make sure that the recursive calls therein use indices beyond the old offset
Here's my untested psuedo-code take on that.
hard( a, i ) ≡ hardHelper( a, a.length ).second( i )
hardHelper( a, 0 ) ≡ ( 1, { case 0 => [] } )
hardHelper( a, n + 1 ) ≡
let t = a[n + 1].length
and ( k, f ) = hardHelper( a, n )
and k' = k * ( t - 1 )
and f'( i ) =
if ( i < k' )
then easyInduction( f, 1 )( a, n + 1, i )
else if ( k' <= i < k' + k )
then easyInduction( f, 1 )( a[ 0..n ] ++ [ [ null ] ], n + 1, i - k' )
else easyInduction( ( b, m, j ) => f( b, m, j + k ), 0 )( a, n + 1, i - k' - k )
in ( k', f' )