### 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:

(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

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

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

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

or something to that effect.

UPDATE: Not fold,

The funky parentheses and `` are the way to construct a

then you can create two sections from

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**.

**(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

**choose**.
## Comments