As the code stands, it's set up to say that if

**a**is in the type class

**Semilattice**, you can create a

**SearchTree**of

**a**s that you can efficiently search. What we want to say is that if you have some type

**a**that has a function

**key :: a -> b**where

**b**is in the type class

**Semilattice**, you can create a

**SearchTree**of

**a**s that you can efficiently search based on the result of

**key**. Then, if we have a list of (palindrome, position) pairs, our key function is just

**fst**(the function that gives you the first item in a pair). Now, how to express that in Haskell?

UPDATE: come to think of it, wouldn't that subsume the existing cases? For them,

**let key = id**

UPDATE: OK, I should have remembered. You can create relationships between type classes. (Take a look at this diagram of relationships among types and type classes in the Standard Prelude.) So, it looks like I can say something like this:

**{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}**

class Semilattice a where

meet :: a -> a -> a

class Semilattice k => Keyed r k | r -> k where

key :: r -> k

class Semilattice a where

meet :: a -> a -> a

class Semilattice k => Keyed r k | r -> k where

key :: r -> k

The first type class definition is straight from Mr. van Laarhoven's code; a type is a

**Semilattice**type if it has a

**meet**function which satisfies the semilattice requirements for meet.

**Keyed**is a "multiparameter type class"; it sets up a relationship between a type

**r**(intended to suggest "record") and a type

**k**(intended to suggest "key"). "

**r -> k**" is a "functional dependency". Those two features aren't in the Haskell 98 standard, but GHC supports them (if they're enabled in a pragma) and I suspect they're in Haskell'.

(Historical aside: you might not realize that the preceding paragraphs use terms that originate with Algol 68: "standard prelude" and "pragma". Algol 68 is a language that suffered from a lot of undeserved bad press; you really should read C.H. Lindsey's excellent paper on its history, and check out Algol 68 Genie. For those of you interested in functional programming, I should note that partial parametrization was up for addition to the standard and is implemented in Algol 68 Genie.)

So, I will proceed on this basis. It should be a simple rewrite of the Semilattice tree code, though I wish there were a way to have one version of it to do everything; code reuse is a Good Thing. The above lines make it past ghci, so I hope it's a good start. (Then, of course, the question is whether it really does help the Fair and Square program! OTOH, in a way I don't care, because the real goal was to learn more Haskell, not to mention that I was just lucky that the original blog post gave an example in which the Semilattice type was a pair.)