By golly...

...I think van Laarhoven's data structure is the way to go.

You'll recall that his "Search trees without sorting" stores the upper bounds of trees to speed up queries of the form "what's the first item with a key >= some value?" If we label the sorted d-digit Ys with their ordinal position:

addOrd :: [a] -> [(Int, a)]

addOrd xs = addOrd' xs 1
    where  addOrd' []   _ = []
           addOrd' x:xs n = (n, x) : addOrd' xs (n + 1)

(Is there a slick way to do that with a fold?  I'll have to look for one. UPDATE: no, but there's still a better way; see below)

then we put the results into one of van Laarhoven's semilattice trees and have

ysInRange m n d
   | nval == n = nPos - mPos + 1
   | otherwise = nPos - mPos
   where (mPos, mVal) = -- first entry w/ d-digit Y >= m
         (nPos, nVal) = -- first entry w/ d-digit Y >= n

OK, not quite, since n may be greater than the last d-digit Y, so we'd have to take care of that case--the easiest way would be to add a sentinel fake Y with value 10^d - 1 (i.e. tweak addOrd to add the sentinel value as a parameter that would be used in the base case).

ERRATUM: make that 10^d; we don't want anything to actually match the sentinel.

And BTW, on the way home from work it occurred to me that while Haskell's Maybe monad is the canonical way to indicate failure, you have to deal with the case in which you do find an actual Y that is greater than the upper bound, so I think a sentinel is better than Nothing.

UPDATE: Darn it, that sentinel will interfere with the lovely functioning of van Laarhoven's semilattice tree, because its maximum possible value swamps everything else. This needs a little more thought.

UPDATE: And indeed, the thing to do is create a data type that has a search tree and a separate sentinel. Then our search function returns

  case findFirst Ge n yTree of
    Just x  -> x
    Nothing -> sentinel

or something to that effect.

UPDATE: Not fold, zip:

addOrd = ([1..] `zip`)

zip takes two lists and gives you back a list of ordered pairs of corresponding elements, going on as long as there are corresponding elements. For example:

zip [1, 2, 4] [-1, 1, -1, 42] results in [(1, -1), (2, 1), (4, -1)]

The funky parentheses and `` are the way to construct a section. If you have a function f,

f :: a -> b -> c

then you can create two sections from f, one with an a value and one with a b value:

• (aValue `f`) bValue results in f aValue bValue.
• so does (`f` bValue) aValue.

 More concrete examples:

• (2 *) is a function that returns twice the value passed it
• (^ 2) is a function that returns the square of the value you pass it

The `` are just how you can use a normally prefix function as infix. We've been doing it all along with choose.