Well, what we want, is a list of all possible products, right? So, we we want a list of lists of Peg, or a [[Peg]].
Well, our first two cases for Red - Purple are pretty easy.
A list of length 0 lists of Peg is just an empty lists of lists, or [[]].
A list of length 1 lists of lists of Peg is each individual item in our sum type of Peg, in a singleton list. That seems obnoxious to type out, so we'll import transpose from Data.List, and derive an Enum class for Peg, giving us transpose [Red .. Purple] as our answer.
So, so far, we've got:
import Data.List (transpose)
data Peg = Red | Green | Blue | Yellow | Orange | Purple
deriving (Show, Eq, Ord,Enum)
nCombos n
| n < 0 = error "Cannot generate negative length list"
| n ==0 = [[]]
| n == 1 = transpose [[Red .. Purple]]
| otherwise = error "I didn't get this far yet."
But now we need every possible combination of length n lists... Well, it just so happens that Haskell gives us a really quick and easy way to generate powersets from component lists, it's called the Applicative typeclass, which has a baked in instance for the [] type.
Lets take a quick break to learn about how that works.
The workhorse of the Applicative typeclass is the (<*>) operator, possessing type: (<*>) :: f (a -> b) -> f a -> f b
So, for lists, it has the following signature:
(<*>) :: [a -> b] -> [a] -> [b]
It works like so:
λ>[(+1)] <*> [1,2,3]
[2,3,4]
λ>[(+)] <*> [1,2,3] <*> [1,2,3]
[2,3,4,3,4,5,4,5,6]
So, as we can see, it applies the (f b) from the right to everything on the left. So this means that we get a powerset of all of the arguments in the chain of (<*>) operators, finally fed into the function on the left.
So, the basic idea us that in [a], [b] and [a->b->c] we can get every possible product of a and b.
Seems like we can leverage that to get us what we need...
For 2 length lists, we'll want to concatenate every length 1 [Peg] with every other other length 1 [Peg].
That's pretty easy to do -
kickIt n = [(++)] <*> (transpose [n]) <*> (transpose [n])
λ>kickIt [Red .. Purple]
[[Red,Red],[Red,Green],[Red,Blue],[Red,Yellow],[Red,Orange],[Red,Purple],[Green,Red],[Green,Green],[Green,Blue],[Green,Yellow],[Green,Orange],[Green,Purple],[Blue,Red],[Blue,Green],[Blue,Blue],[Blue,Yellow],[Blue,Orange],[Blue,Purple],[Yellow,Red],[Yellow,Green],[Yellow,Blue],[Yellow,Yellow],[Yellow,Orange],[Yellow,Purple],[Orange,Red],[Orange,Green],[Orange,Blue],[Orange,Yellow],[Orange,Orange],[Orange,Purple],[Purple,Red],[Purple,Green],[Purple,Blue],[Purple,Yellow],[Purple,Orange],[Purple,Purple]]
But now we need a way to take [[Pegs]] and add all other possible combinations with another set of the [Peg] singletons... Well, so we want to take type [[Peg]] and return type [[Peg]]. That sounds like a job for iterate -
iterate :: (a -> a) -> a -> [a]
There is a neat little haskell idiom for feeding something to itself x times -
\f acc n -> (iterate f acc) !! n
Or, generate an infinite list execute f on it's own result, starting with value acc, and give me the nth item.
So, now we use what we know about the applicative operator, and partial application, to build our iterable function ...
keepRolling l r = ([(++)] <*> transpose [n] <*> r)
And then we put it all together:
import Data.List (transpose)
data Peg = Red | Green | Blue | Yellow | Orange | Purple
deriving (Show, Eq, Ord,Enum)
kickIt n = [(++)] <*> (transpose [n]) <*> (transpose [n])
keepRolling l r = ([(++)] <*> transpose [n] <*> r)
nCombos n
| n < 0 = error "Cannot generate negative set"
| n ==0 = [[]]
| n == 1 = transpose [[Red .. Purple]]
| otherwise = iterate (keepRolling [Red .. Purple]) (kickIt [Red .. Purple]) !! (n - 2)
