**meet**operation on it that satisfies the semilattice properties, so it can take its rightful place in the

**Semilattice**type class. Then we can use

**fromList**to create a tree and search it.

(By the way, we've gone a long way with just a few built-in types. Initially we were using floating point, but that was in fact a bug because of the size of the integers we have to deal with. That leaves

**Int**(fixed-size integer),

**Integer**(arbitrary-precision integer aka "bignum"), and lists. Aside from Lisp, how many of the languages atop the TIOBE Index could one do this in purely with built-in types?)

So, how do you create a type in Haskell?

In our earlier code fragment, we supposed we could use a

**(Int, Integer)**to hold a d-digit Y value and its ordinal position in the list of all d-digit Y values (though not in that order!). Perhaps we can use

**type**, which just lets you refer to a type by a name of your choice. That name becomes a "synonym" for the type:

**type TaggedY = (Int, Integer)**

Will that do? Not for us, alas. The whole point is to create an instance of

**Semilattice**, and the fine print of

**instance**says "...furthermore, [the type you're declaring to be an instance of a type class] must not be a type synonym" (Haskell 2010 Report, 4.3.2, "Instance Declarations"). Shucks!

What now? We have two choices:

**newtype**or

**data**.

**newtype**is what the Haskell Report refers to as a data type "renaming". Unlike

**type**, it gives an actual constructor that you have to use to create something of the new type, and I suspect that is what lets you say a

**newtype**type is an instance of a type class.

**newtype TaggedY = MakeTaggedY (Int, Integer)**

We're really just renaming

**(Int, Integer)**, so we'll take this route. We don't need the added power of

**data**.

The ordinal position is just along for the ride, so for us,

**meet**is just the maximum of the Ys... but wait. If you take a look, van Laarhoven already has

**newtype Max a = Max { getMax :: a } deriving (Show)**

**instance Ord a => Semilattice (Max a)**

**where meet (Max a) (Max b) = Max (max a b)**

**newtype Ge a = Ge a deriving (Show)**

**instance Ord a => Satisfy (Ge a) (Max a)**

**where satisfy (Ge q) = (>= q) . getMax**

Huh? He's setting up the general case of what we want to do.

That first newtype doesn't look quite like ours:

- It's
*polymorphic*, i.e. it works for any type in**Ord**. This is serious DRY, and Haskell makes it easy. van Laarhoven does here what should be my goal as I advance in Haskell. - What's that
**{getMax :: a}**? We've seen something like the insides before; it says**getMax**has type**a**, but what does it mean in this context? You have to read a bit further through the report than I expected; in this context it's a deconstructor. If**x**has type**a**, then**Max x**stuffs it into a**Max a**which it returns; if**y**has type**Max a**,**getMax****y**gives you back the value of type**a**it contains. **deriving (Show)**?**Show**is the class of types that have printable representations. Remember that quick-and-dirty**backwards**,**read . reverse . show**? The ticket for**a**'s admission to**Show**is a**show**function that you can hand an**a**and get back a**String**that represents it (and, if**a**is in**Read**, ideally**read . show**should be a (kind of slow) equivalent of**id :: a**, where**id**is the identity function, as you probably figured out). Haskell can figure out how to**show**some types for you, so you don't have to write your own, and this is one case.

**instance**lines are what we're really after. The first one says "if

**a**is in the type class

**Ord**(the one for things that have a total order), then

**Max a**is a

**Semilattice**with

**max**(working on the

**a**values therein) as the meet function".

The second sets you up for queries looking for values greater than or equal to a given value. The

**Max a**values in the tree get fed to

**getMax**to extract the

**a**, and then get compared with

**m**.

But enough talk. I should have the courage of my convictions, and actually make the move to what should make the search through generated Ys take time on the O(

**logBase 2 (numNDigitYs n)**) instead of O(

**numNDigitYs n**). Back when the smoke clears.