For certain classes of problems where speed is of the essence, table lookups can be a fantastic solution. However, many functional programmers eschew these approaches partly because they are thinking in terms of lists, and lookups in lists (as we all know) are a bit rubbish most of the time. However, Haskell has a fantastic array implementation that is flexible enough to put many imperative languages to shame (especially when combined with list comprehensions). Hopefully an example will illustrate what I mean. The actual array lookup I'm doing is into arrays of much larger size, but the principle is exactly the same.

Say you want to model a regular deck of 52 playing cards and want to write functions to convert them to and from integers. We want to proceed by rank (two to ace), then for each rank, by suit (clubs, diamonds, hearts, spades) so the two of clubs is going to be 0, the two of spades is going to be 3 and the ace of spades is going to be 51.

Let's start by defining the datatypes for Rank and Suit and a simple generic card type:

``````data Rank =
Two
| Three
| Four
| Five
| Six
| Seven
| Eight
| Nine
| Ten
| Jack
| Queen
| King
| Ace
deriving (Eq, Ord, Show, Read, Enum, Ix)

data Suit =
Clubs
| Diamonds
| Hearts
deriving (Eq, Ord, Show, Read, Enum, Ix)

data GenCard = GenCard Rank Suit
``````

...so far so not very interesting. Now the two functions we want to define are:

``````genCardOfInt :: Int -> GenCard
genCardToInt :: GenCard -> Int
``````

...and obviously, you could do:

``````genCardOfInt 0 = GenCard Two Clubs
genCardOfInt 1 = GenCard Two Diamonds
``````

...etc all the way to...

``````genCardOfInt 51 = GenCard Ace Spades
``````

...and then...

``````genCardToInt (GenCard Two Clubs) = 0
``````

...and so on.

This would work, but it is extremely smelly. The thing that alerts us to the fact that this is fishy is that there is a lot of repetitive typing. The gods of Haskell frown on this and generally if you're doing a bunch of it, there's probably something wrong. And indeed there is. This approach leads to a linear search through cases every time until we find a match. If we care about performance, this will be horrible and imagine how bad it will get if we get a table with (say) 4 million entries? The actual problem I am interested in requires this size of table. Happily we can use an array-driven method to not only speed up our algorithm, but also to scrap all this tedious repitition. First, some background.

For genCardOfInt what we want to do is create an array of 52 cards and then use the int passed in to look up into this array. This will give us constant time access. So what we want is:

``````genCardOfInt x = lookup ! x
where
lookup = .... to be discussed
``````

One possible solution is to do

``````        lookup = listArray (0,51) [GenCard Two Clubs, GenCard Two Diamonds etc etc etc]
``````

... but that's almost as unhaskelly as what we had before! So, here's how we do it.

``````genCardOfInt x = lookup ! x
where
lookup = listArray (0,51) [GenCard r s|r<-enumFrom Two, s<-enumFrom Clubs]
``````

Say whaaaa? Well, let's see what ghci has to say:

``````*Card> enumFrom Two
[Two,Three,Four,Five,Six,Seven,Eight,Nine,Ten,Jack,Queen,King,Ace]
*Card> enumFrom Clubs
``````

So because we said "deriving Enum" for our types, we get this ability for free. Mighty 'andy.

``````*Card> [GenCard r s|r<-enumFrom Two, s<-enumFrom Clubs]
``````

So that bit is a list comprehension. Basically it's a simple way of defining a list and avoids all the tedium and boilerplate. And "listArray" takes some dimensions and a list and returns an array. But the best is yet to come, and ghci hints at it now:

``````*Card> :t listArray (0,51) [GenCard r s|r<-enumFrom Two, s<-enumFrom Clubs]
listArray (0,51) [GenCard r s|r<-enumFrom Two, s<-enumFrom Clubs]
:: (Num t, Ix t) => Array t GenCard
``````

So the type of that "lookup" variable is an Array t GenCard. The "t" is some numeric type that we can use to index into our array, and the GenCards (as we know) are what's in the array. So the type of the array index is polymorphic.

This means we can do:

``````genCardToInt :: GenCard -> Int
genCardToInt (GenCard r s) = lookup ! (r,s)
where
``````

Gosh! Let's try that expression in ghci:

``````*Card>  listArray ((Two,Clubs),(Ace,Spades)) [x|x<-[0..51]]