《函数式编程导论》习题：choose k xs的递归定义及组合数证明

Let's tackle this problem from Bird-Wadler's Introduction to Functional Programming step by step—first the recursive definition of choose, then the combinatorial proof you need, and a quick note on your non-recursive approach.

Recursive Definition of choose #

The core recursive idea splits the problem into two choices for the first element of the list: include it in the subsequence, or exclude it. We also need clear base cases to terminate the recursion cleanly.

Here's the Haskell implementation following this logic:

choose :: Int -> [a] -> [[a]]
-- Base case 1: Choosing 0 elements from any list gives exactly the empty subsequence
choose 0 _ = [[]]
-- Base case 2: Choosing any positive number of elements from an empty list is impossible
choose k [] = []
-- Recursive case: Split into including or excluding the first element
choose k (x:xs)
  -- Edge case: If k is larger than the list length, return nothing
  | k > length (x:xs) = []
  | otherwise = 
      -- Include x: prepend x to all subsequences of length k-1 from the rest of the list
      map (x:) (choose (k-1) xs) 
      ++ 
      -- Exclude x: take all subsequences of length k from the rest of the list
      choose k xs

Testing this with your example choose 3 "list":

• We include 'l' and pick 2 elements from "ist" → gives ["lis", "lit", "lst"]
• We exclude 'l' and pick 3 elements from "ist" → gives ["ist"]
• Combining these gives the correct set of subsequences (order may vary, but all required elements are present).

Proof that length (choose k xs) = C(n,k) where n = length xs #

We'll use mathematical induction on the length n of the input list xs.

Base Cases #

1. When n = 0 (empty list):
   • If k = 0: choose 0 [] = [[]], length 1. C(0,0) = 1 → matches.
   • If k > 0: choose k [] = [], length 0. C(0,k) = 0 → matches.
2. When k = 0:
   • For any list xs, choose 0 xs = [[]], length 1. C(n,0) = 1 for any n → matches.
3. When k > n:
   • choose k xs = [], length 0. C(n,k) = 0 (you can't choose more elements than exist) → matches.

Inductive Step #

Assume that for all lists of length n, length (choose k xs) = C(n,k) for any valid k. Now consider a list x:xs of length n+1.

For 0 < k ≤ n+1:

• By the recursive definition, length (choose k (x:xs)) = length (map (x:) (choose (k-1) xs)) + length (choose k xs)
• The map function doesn't change list length, so length (map (x:) (choose (k-1) xs)) = length (choose (k-1) xs)
• By our inductive hypothesis, length (choose (k-1) xs) = C(n, k-1) and length (choose k xs) = C(n,k)
• Using the binomial coefficient recurrence relation: C(n+1,k) = C(n,k-1) + C(n,k)
• Therefore, length (choose k (x:xs)) = C(n+1,k) → which is exactly what we needed to prove.

Side Note on Your Non-Recursive Approach #

Your approach of generating all subsets first and filtering for length k works, but it's less efficient—since you generate exponentially more subsets than you actually need. For example, generating all subsets of a 10-element list gives 1024 results, but choose 5 [1..10] only needs 252 of them. The recursive approach builds only the subsequences you require, making it much more performant for larger lists.

内容的提问来源于stack exchange，提问作者acontell