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

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

1 голос
/ 12 февраля 2010

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

4 голосов
/ 12 февраля 2010

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

    [ 
        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
}
2 голосов
/ 12 февраля 2010

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

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

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

1 голос
/ 12 февраля 2010

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

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

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

...