Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell: How to generate a cartesian product of two simple algebraic data types

I am learning Haskell, so I'm writing some simple card games. I've defined some data types:

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

data Suit = Hearts|Spades|Diamonds|Clubs deriving (Show)

data Card = Card Rank Suit 

Now I'd like to create a pristine deck of 52 cards. I'm sure there is a slick way to do it, but all I can come up with is:

 pristineDeck = [Card Ace Hearts, Card Two Hearts, ...]

Can I get Haskell to generate this list for me?

like image 692
Tony K. Avatar asked Jan 04 '13 23:01

Tony K.


3 Answers

List comprehensions are a very tidy syntax for this. If you derive Enum on Rank and Suit you can express it very simply as:

pristineDeck = [ Card rank suit | suit <- [Hearts .. Clubs], rank <- [Ace .. King] ]

If you're wondering why I have suit and rank in different orders, the first is because of the order the Card constructor uses, while the latter is to get the order of the resulting list--suits together in ascending order.

In more generality, or when a single list comprehension gets too bulky, the cartesian product is exactly the behavior given by the Monad instance for lists. The following is equivalent to the list comprehension above:

pristineDeck = do suit <- [Hearts .. Clubs]
                  rank <- [Ace .. King]
                  return $ Card rank suit

As one other minor point, to save yourself the trouble of remembering what order the Suit values are in, deriving Bounded as well will enable to write [minBound .. maxBound] to enumerate all values of any type with instances of both Enum and Bounded.

like image 71
C. A. McCann Avatar answered Nov 08 '22 12:11

C. A. McCann


There are several ways to do this, of varying amounts of wizardry.

Firstly, since none of the constructors of your types have arguments, you can derive Enum for them. This will allow you to write e.g. [Ace..King] to get a list of all cards.

Secondly, list comprehensions are a great way to form a list of items drawn from multiple other lists. Try this:

[x + y | x <- [100,200,300], y <- [1,2,3]]

That should give you the tools you need to apply to your example.

like image 24
Ben Millwood Avatar answered Nov 08 '22 12:11

Ben Millwood


Alp is correct on tell you to derive Enum

>data Rank = Ace|Two|Three|Four|Five|Six|Seven|Eight|Nine|Ten|Jack|Queen|King deriving (Eq,Show,Ord,Enum)
>data Suit = Hearts|Spades|Diamonds|Clubs deriving (Show,Enum)

Now:

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

To get the permutations of two lists you can use a list comprehension:

>[[x,y]|x<-[1..2],y<-[2..5]]
[[1,2],[1,3],[1,4],[1,5],[2,2],[2,3],[2,4],[2,5]]

or to get the permutations of addition:

>[x + y|x<-[1..2],y<-[2..5]]
[3,4,5,6,4,5,6,7]

Now you just need to do a few substitutions to get the permutations of Car with Rank and Suit.

like image 3
Davorak Avatar answered Nov 08 '22 12:11

Davorak