Is there an existing template for creating a list of function applications for each combination of elements in two lists?

Question

I just go into functional programming and I’m in the section “Try some non-trivial examples and ask others if I am doing it wrong”. I follow Don Syme F # Tutorial and decided to hit the blackjack exercise at the end of the second part with a twist: he suggests treating Ace as 11 for simplicity, but I decided to ignore this recommendation.

The way I handle this is to give each map a list of possible values ​​and recursively create a list of possible manual values:

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 handValues so similar in structure to a fold that I cannot shake the feeling that there is already some kind of high-order function that I can use to achieve this. Is there something I'm missing or is this pretty much the right direction?

Answer 1

It is worth noting aside that this

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

- monadic binding; one could write the monad "list" and then use the expression of the calculation to write it as

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

Answer 2

The way you do is beautiful. You can express any recursive function in lists as a fold, but I don’t think you get anything by doing it here. There is also no built-in function to do exactly what you need, but you could build a more general function and build your own calculation on top of it. Here is 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 every possible list containing one element from each (for example, 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 cards in hand, and then summarize each such list.

There are probably several other ways to look at a problem that other options might offer.

Answer 3

I think your decision is already good.

Fold does not work in your case. We can add a list of numbers, we can also add two lists of numbers. But in your case, these are not just two lists of numbers.

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