Baby's First Type

If we're going to use van Laarhoven's trees, we have to create a type and define a 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.

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