関数型プログラミングの初級問題-26問目- 「組合せ」

　プログラミング初心者が挑戦する関数型プログラミングによるリスト操作の練習問題の26問目です。問題は、OCaml公式ページのものを使いました。
　内容は、問題と答案です。答案の作成時間は、2日でした。

問題26.

　長さnのリストからk個の要素を「順序を問わず、かつ重複を許さず」に選び出してなるリストからなるリストを生成する関数extractを書け（「順序を問わず、かつ重複を許さず」とは所謂組合せのことです）。

※ 例えば、extract 2 ["a"; "b"; "c"]は[["a"; "b"]; ["a"; "c"]; ["b"; "c"]]になります。

答案

基本的な考え方

　関数型プログラミングによるリスト操作の基本的な流れは、以下の1から3になります。
　　1. 引数のリストをheadとtailに分離する
　　2. tailを引数として再帰呼び出すると共に、その返り値とheadを適当に組み合わせる
　　3. 以上を引数のリストが停止条件に達するまで繰り返す

本問の解き方

　以下の説明では、所与のリストの長さをn、選び出す要素の数をkとします。
　また、関数extractにより生成されるべき「リストのリスト」を入れ子リストと呼びます。

　ここで、所与のリストに対しいずれの要素とも重複しない要素を追加し、かつ選び出す要素の数をk+1にしたとします。

　このとき、関数extractにより生成されるべき「リストのリスト」は、
　1. 入れ子リストの各リストに追加要素を結合したリスト
　2. 所与のリストに対するk+1の組合せのリスト
からなります。

　つまり、1.がリストの長さについての再帰的な構成を表し、2.が要素の数についての再帰的な構成を表します。

コード

let rec extract n lisuto =
 let rec append youso = function
  | [] -> []
  | head::tail -> (youso::head)::append youso tail in

 let rec nest = function
  | [] -> []
  | head::tail -> [head]::nest tail in

 if n = 1 then nest lisuto else match lisuto with
  | [] -> []
  | head::tail -> append head (extract (n-1) tail)@(extract n tail)

コード（改訂）

let rec map f = function [] -> []
 | head::tail -> f head::map f tail

let rec comb n l =
 if n = 1 then map (fun x -> [x]) l
 else match l with [] -> []
  | head::tail -> (map (fun y -> head::y) (comb (n-1) tail))@comb n tail

　関数appendと関数nestを無名関数にしました。

感想

　今回の記事は書き直しです。

　初めに上げた記事の答案が間違っていました。次の問題27.を解く際に、いつもの如く今回の答案を使い回そうとして気付きました。

　また、記事ではぐだぐだと誰も読みたがらないような言い訳と不満をだらだらと書いていました。
　以上から当初記事を削除し、新たに書き直すこととしました。

　これで何だか問題をあっさり解いた感じになりました。まあ、説明は相変わらず意味不明ですが。

　次回は、第27問です。
　ここまで読んだ読者のなかに、どなたかプログラミング上級者はおられませんか？今回の問題を再帰的にスッキリと解説していただきたいのですが。
　解説していただけたら、それを丸パクリして
　「東大生の正答率0.1％の超難問？を分かりやすく解説してみた」
という有料記事にしたいです。ちなみに東大とは「ひがだい」東淀川大学のことです。