### Baby's First Type

If we're going to use van Laarhoven's trees, we have to create a type and define a

(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

So, how do you create a type in Haskell?

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

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

What now? We have two choices:

We're really just renaming

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

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

That first newtype doesn't look quite like ours:

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

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(

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