두 개의 목록에있는 항목의 모든 조합에 함수의 응용 프로그램 목록을 생성하는 기존 패턴이 있습니까?

Question

저는 방금 함수 프로그래밍을 시작했습니다. "나는 잘못하고있는 예제를 시험해보고 다른 사람들에게 내가 잘못했는지 묻습니다."단계에 있습니다. Don Syme의 다음 글 인 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 기능은 구조가 매우 유사하다 내가 이것을 달성하기 위해 사용할 수있는 고차 함수가 이미 있다는 느낌을 떨칠 수없는 배. 내가 누락 된 부분이 있습니까, 아니면 거의 올바른 방향입니까?

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

나는 당신의 해결책이 이미 좋다고 생각합니다.

폴드가 작동하지 않습니다. 우리는 숫자의 목록을 접을 수 있으며, 두 개의 숫자 목록을 접을 수도 있습니다. 그러나 귀하의 경우에는 숫자의 두 가지 목록 만이 아닙니다.

귀하의 목록에 길이가 n 인 모든 에이스가 포함 된 극단적 인 경우를 생각해 볼 때 2^n 개의 가능한 값이 있습니다. 모든 가능성을 열거하려면 dfs 검색 또는 bfs 검색이 필요합니다. 재귀적인 방법으로 작성하더라도 코드는 실제로 bfs 검색과 같습니다 (따라서 더 많은 메모리가 필요합니다).

Answer 3

당신이하는 일은 완벽합니다. 목록에있는 모든 재귀 함수를 접는 식으로 표현할 수도 있지만 여기에서 그렇게하면 아무 것도 얻을 수 없다고 생각합니다. 필요한 기능을 정확히 수행 할 수있는 내장 함수가 없지만보다 일반적인 함수를 작성하고 그 위에 특정 계산을 작성할 수 있습니다.

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]])에서 하나의 원소를 함유하는 각 가능한 목록을 반환 한 다음 이러한 접근 방법. 우리는이 함수를 사용하여 손에 든 카드의 모든 가능한 값 목록을 얻은 다음 각 목록을 합계합니다.

다른 변형을 제안 할 수있는 몇 가지 다른 방법이 있습니다.