Существует ли существующий шаблон для создания списка применений функции для каждой комбинации элементов в двух списках?

Я только вхожу в функциональное программирование, и я нахожусь в стадии "попробуй некоторые нетривиальные примеры и спроси других, делаю ли я это неправильно". Я следую учебнику Дона Сайма по F# и решил сделать удар в упражнении с блэкджеком в конце части II с изюминкой: он предлагает рассматривать 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 ответа

Решение

Стоит отметить, что это

    [ 
        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
}
Источник

То, как вы делаете вещи, прекрасно. Любую рекурсивную функцию в списках можно выразить в виде сгиба, но я не думаю, что вы добьетесь этого, делая это здесь. Там также нет встроенной функции, чтобы делать именно то, что вам нужно, но вы могли бы построить более общую функцию и построить свой конкретный расчет на этом. Вот один из таких подходов:

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]]). Мы используем эту функцию, чтобы получить все возможные списки значений для карт в руке, а затем суммировать каждый такой список.

Возможно, есть несколько других способов взглянуть на проблему, которые могут предложить другие варианты.

Источник

Я думаю, что ваше решение уже хорошо.

Сложите не работает в вашем случае. Мы можем сложить список чисел, мы также можем сложить два списка чисел. Но в вашем случае это не просто два списка чисел.

Рассмотрим крайний случай, когда ваш список содержит все тузы с длиной n, тогда есть 2^n возможных значений. Чтобы перечислить все возможности, вам нужен поиск по dfs или поиск по bfs. Ваш код фактически эквивалентен поиску BFS (поэтому он стоит больше памяти), хотя он пишет рекурсивным способом.

Источник
Другие вопросы по тегам