Haskell arrays are amazing

Functional languages are all about lists... but Haskell has incredible arrays

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 =
    | Three
    | Four
    | Five
    | Six
    | Seven
    | Eight
    | Nine
    | Ten
    | Jack
    | Queen
    | King
    | Ace
    deriving (Eq, Ord, Show, Read, Enum, Ix)

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

data GenCard = GenCard Rank Suit
    deriving (Eq, Ord, Show, Read)

...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
        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
        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
*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]
[GenCard Two Clubs,GenCard Two Diamonds,GenCard Two Hearts,GenCard Two Spades,GenCard Three Clubs,GenCard Three Diamonds,GenCard Three Hearts,GenCard Three Spades,GenCard Four Clubs,GenCard Four Diamonds,GenCard Four Hearts,GenCard Four Spades,GenCard Five Clubs,GenCard Five Diamonds,GenCard Five Hearts,GenCard Five Spades,GenCard Six Clubs,GenCard Six Diamonds,GenCard Six Hearts,GenCard Six Spades,GenCard Seven Clubs,GenCard Seven Diamonds,GenCard Seven Hearts,GenCard Seven Spades,GenCard Eight Clubs,GenCard Eight Diamonds,GenCard Eight Hearts,GenCard Eight Spades,GenCard Nine Clubs,GenCard Nine Diamonds,GenCard Nine Hearts,GenCard Nine Spades,GenCard Ten Clubs,GenCard Ten Diamonds,GenCard Ten Hearts,GenCard Ten Spades,GenCard Jack Clubs,GenCard Jack Diamonds,GenCard Jack Hearts,GenCard Jack Spades,GenCard Queen Clubs,GenCard Queen Diamonds,GenCard Queen Hearts,GenCard Queen Spades,GenCard King Clubs,GenCard King Diamonds,GenCard King Hearts,GenCard King Spades,GenCard Ace Clubs,GenCard Ace Diamonds,GenCard Ace Hearts,GenCard Ace Spades]

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)
        lookup = listArray ((Two,Clubs),(Ace,Spades)) [x|x<-[0..51]]

Gosh! Let's try that expression in ghci:

*Card>  listArray ((Two,Clubs),(Ace,Spades)) [x|x<-[0..51]]
array ((Two,Clubs),(Ace,Spades)) [((Two,Clubs),0),((Two,Diamonds),1),((Two,Hearts),2),((Two,Spades),3),((Three,Clubs),4),((Three,Diamonds),5),((Three,Hearts),6),((Three,Spades),7),((Four,Clubs),8),((Four,Diamonds),9),((Four,Hearts),10),((Four,Spades),11),((Five,Clubs),12),((Five,Diamonds),13),((Five,Hearts),14),((Five,Spades),15),((Six,Clubs),16),((Six,Diamonds),17),((Six,Hearts),18),((Six,Spades),19),((Seven,Clubs),20),((Seven,Diamonds),21),((Seven,Hearts),22),((Seven,Spades),23),((Eight,Clubs),24),((Eight,Diamonds),25),((Eight,Hearts),26),((Eight,Spades),27),((Nine,Clubs),28),((Nine,Diamonds),29),((Nine,Hearts),30),((Nine,Spades),31),((Ten,Clubs),32),((Ten,Diamonds),33),((Ten,Hearts),34),((Ten,Spades),35),((Jack,Clubs),36),((Jack,Diamonds),37),((Jack,Hearts),38),((Jack,Spades),39),((Queen,Clubs),40),((Queen,Diamonds),41),((Queen,Hearts),42),((Queen,Spades),43),((King,Clubs),44),((King,Diamonds),45),((King,Hearts),46),((King,Spades),47),((Ace,Clubs),48),((Ace,Diamonds),49),((Ace,Hearts),50),((Ace,Spades),51)]

So we have an array which is indexed by a pair of (Rank, Suit), and the values are numbers from 0 to 51. And no boilerplate. If we wanted to test this, of course, we could write some quickcheck properties that verify this implementation against the naive one I gave before. This sort of model-based testing is going to be essential to verify the complex but fast implementation I have for my real problem against the obvious but insanely verbose and slow implementation that I can put in my test.

Aren't Haskell arrays amazing though? I was genuinely stunned when I realised I could do table-driven methods so elegantly. There's a nice tutorial to Haskell arrays in the "gentle introduction"

Unless otherwise specified the contents of this page are copyright © 2015 Sean Hunter. This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.