代码之家 › 专栏 › 技术社区 › Cogwheel

是否有一个现有的模式来生成一个函数的应用程序列表,用于两个列表中项目的每个组合?

terminology functional-programming f#

1

Cogwheel · 技术社区 · 16 年前

我刚开始学习函数式编程,现在正处于“尝试一些不平凡的例子,并询问其他人我是否做错了”阶段。我跟着唐·赛姆 F# Tutorial 在第二部分的结尾,我决定尝试一下21点的练习:为了简单起见,他建议将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 函数在结构上与折叠非常相似,以至于我无法摆脱这样的感觉:已经有了一些高阶函数,我可以用它来实现这一点。有什么东西我找不到了,还是这个方向很正确?

3 回复 | 直到 16 年前

1

4

Brian 16 年前

值得一提的是,

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

是一个单元绑定;可以编写一个“list”单元,然后使用计算表达式将其编写为

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

2

kvb 16 年前

你做事的方式很好。可以将列表上的任何递归函数表示为折叠,但我认为在这里这样做不会获得任何好处。也没有内置函数可以精确地执行您需要的操作,但是您可以构建一个更通用的函数,并在此基础上构建您的特定计算。下面是一个这样的方法:

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]] )我们使用这个函数来获取一手牌的所有可能值列表,然后对每个列表求和。

您可能还有其他几种方法来看待这个问题,它们可能会提示其他的变化。

3

1

Yin Zhu 16 年前

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

折叠在您的情况下不起作用。我们可以折叠一个数字列表,也可以折叠两个数字列表。但在你的例子中,它不仅仅是两个数字列表。

考虑一个极端情况,您的列表包含长度为n的所有ace,那么可能有2^n个值。要枚举所有可能性,您需要一个DFS搜索或BFS搜索。您的代码实际上相当于bfs搜索(因此它需要更多的内存),尽管它是以递归的方式编写的。