関数型プログラミングの初級問題-16問目- (約5分)

　関数型プログラミングによるリスト操作の練習問題の16問目です。問題は、OCaml公式ページのものを使いました。
　内容は、問題と答案です。答案の作成時間は、約5分でした。

問題16.

　リストの要素を所定の順番ごとに削除する関数dropを書け。
（先頭からn番目の要素を削除し、次の要素を先頭としてまたn番目の要素を削除し、これを繰り返します。）

※ 例えば、drop ["1"; "2"; "3"; "4"; "5"] 2が["1"; "3"; "5"]になります。

答案

基本的な考え方

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

本問の解き方

　全体的な処理の流れとしては、n番目の要素の前後（n番目は含まれない）でリストを分割し、後半部分のリストについて同じ処理を行い、各処理での前半部分のリストを一つに結合して結果とします。

　順番を指定する引数を保存する必要があるので、要素を数える処理を別関数にします。
　この別関数は、リストと順番nとを引数にとり、n番目の要素の前後でリストを二つに分割してタプルとして返します。

　関数dropでは、別関数の返り値のうち、n-1番以前の要素からなるリストを切片として、n+1番以降のリストを残りリストとして受け取ります。
　これらの切片と、残りリストを引数とした再帰呼び出しの返り値とを@演算子で結合していき、最終的な返り値を生成します。

コード

let rec drop =
let rec segment = fun lisuto n -> match lisuto with
| [] -> ([], [])
| head::tail -> if n <= 1 then ([], tail) else
let (seppen, nokori) = segment tail (n-1) in (head::seppen
, nokori) in
fun lisuto n -> match lisuto with
| [] -> []
| _ -> let (seppen, nokori) = segment lisuto n in seppen@drop nokori n

---

感想

　とても読み難い醜いコードです。

　引数を保存しつつ、その引数を停止条件に使おうとするとどうしても、内部関数が必要になりコードが汚くなります。
　今回の答案で言えば、順番を指定するnがこれに当たります。

　一般に、n回のループ処理を再帰呼出しで行う場合、nを停止条件（n=1）に使わなければなりません。
　しかし、主関数でn=1を停止条件にしてしまうと、n回目のループで終了してしまいます。
　これでは、リストがnよりも長い場合に、2n, 3n…回目のループ処理を行うことができません。

　もしかしたら、このような場合に用いられる関数型プログラミングならではのパターンがあるのかもしれません。

　次回は、第17問です。
　お盆の忙しさで疲労が溜まっているせいか、甘味の写真ばかりを見出しに選んでしまいます、とコメントを書いたのですが、おいしそうな煮豚があったので豚にしました。oink oink　（これを覚えたのはUltimaだったけ、Serpent Isleだったかな）