是否存在现有模式来生成函数对两个列表中项目的每个组合的应用列表？

Question

我刚刚进入函数式编程，并且正处于“尝试一些重要的示例并询问其他人我是否做错了”阶段。我正在关注 Don Syme 的 F# 教程 并决定在第二部分末尾尝试一下二十一点练习：为了简单起见，他建议将 Ace 视为 11，但我决定忽略这一点推荐。

我处理它的方法是为每张牌提供一个可能值的列表，并递归地构建一个可能的手牌值列表：

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
        ]

handValues 函数在结构上与折叠非常相似，因此我无法动摇我已经可以使用一些高阶函数来完成此任务的感觉。我是否缺少某些东西或者这几乎是正确的方向？

Answer 1

值得一提的是，这

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

是一个单子绑定；人们可以编写一个“列表”单子，然后使用计算表达式将其写为

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

Answer 2

你做事的方式非常好。可以将列表上的任何递归函数表示为折叠，但我认为在这里这样做不会获得任何好处。也没有内置函数可以完全满足您的需要，但您可以构建一个更通用的函数并在此基础上构建您的特定计算。下面是一种这样的方法：

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)

allChoices 函数获取一个列表列表，并返回每个可能的列表，其中包含每个列表中的一个元素（例如 allChoices [[1];[2;3];[4 ;5]] = [[1;2;4];[1;2;5];[1;3;4];[1;3;5]])。我们使用此函数获取手牌中所有可能的值列表，然后对每个此类列表求和。

您可能还有其他几种看待问题的方法，这些方法可能会提出其他变化。

Answer 3

我认为你的解决方案已经很好了。

折叠不适用于您的情况。我们可以折叠一个数字列表，也可以折叠两个数字列表。但就您而言，它不仅仅是两个数字列表。

考虑一个极端的情况，你的列表包含所有长度为 n 的 A，那么有 2^n 个可能的值。要枚举所有可能性，您需要 dfs 搜索或 bfs 搜索。您的代码实际上相当于 bfs 搜索（因此会消耗更多内存），尽管它以递归方式编写。