Is there an existing pattern to generate a list of the applications of a function to every combination of the items in two lists?

Question

I'm just getting into functional programming and i'm in the "try out some non-trivial examples and ask others if I'm doing it wrong" phase. I'm following Don Syme's F# Tutorial and have decided to take a stab at the blackjack exercise at the end of Part II with a twist: he suggests treating Ace as 11 for simplicity's sake, but I decided to ignore that recommendation.

The way I'm handling it is by giving each card rank a list of possible values and building up a list of possible hand values recursively thus:

let cardValues (Card(rank, _)) =
    match rank with
    | Ace                 -> [1; 11]
    | King | Queen | Jack -> [10]
    | Value(value)        -> [value]

let rec handValues = function
    | [] -> [0]
    | card::cards ->
        [
            for handValue in handValues cards do
                for cardValue in cardValues card do
                    yield handValue + cardValue
        ]

The handValues function is so similar in structure to a fold that I can't shake the feeling there's already some high order function I can use to accomplish this. Is there something I'm missing or is this pretty much the right direction?

Answer 1

I think your solution is already good.

Fold does not work in your case. We can fold a list of number, we can also fold two list of numbers. But in your case, it is not simply two lists of numbers.

Consider an extreme case that the your list contains all Aces with length n, then there are 2^n possible values. To enumerate all possibilities, you need a dfs search or bfs search. Your code is actually equivalent to a bfs search (so it costs more memory), although it writes in a recursive way.

Answer 2

The way you're doing things is perfectly fine. It's possible to express any recursive function on lists as a fold, but I don't think that you gain anything by doing so here. There's also no built-in function to do exactly what you need, but you could build a more generic function and build your specific calculation on top of that. Here's one such approach:

let rec allChoices = function
| [] -> [[]]
| l::ls ->
    [for x in l do
     for xs in allChoices ls do
       yield x::xs]

let values hand = 
  hand |>
  List.map cardValues |>
  allChoices |> 
  List.map (List.sum)

The allChoices function takes a list of lists and returns each possible list containing a single element from each (e.g. allChoices [[1];[2;3];[4;5]] = [[1;2;4];[1;2;5];[1;3;4];[1;3;5]]). We use this function to get all possible lists of values for the cards in a hand, and then sum each such list.

There are probably several other ways you could look at the problem which might suggest other variations.

Answer 3

It's worth mentioning as an aside that this

    [ 
        for handValue in handValues cards do 
            for cardValue in cardValues card do 
                yield handValue + cardValue 
    ] 

is a monadic bind; one could author a 'list' monad and then use computation expressions to write this as

listMonad {
    let! handVal = handValues cards
    let! cardVal = cardValues card
    return hardVal + cardVal
}