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

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

問題20.

　リストのn番目の要素を削除する関数remove_atを書け。

※ 例えば、remove_at 3 ["0"; "1"; "2"; "3"; "4"]は(["0"; "1"; "2"; "4"])になります。

答案

基本的な考え方

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

本問の解き方

　問題17.の答案の分割関数splitを用います。
　関数spliteは、先頭からn番目でリストを前後に分割してタプルとして返します。
　このとき、n番目の要素はタプルの第2要素の先頭（head）になります。
　そこで、第1要素と第2要素のtailとを結合することで、n番目の要素を削除したリストとなります。

コード

OCaml

let remove_at n lisuto =
 let rec split i = function [] -> ([], []) | head::tail ->
   if i < 1 then ([], head::tail)
   else let (zenhan, kohan) = split (i-1) tail in (head::zenhan, kohan) in
  let (zenhan, kohan) = split n lisuto in zenhan@match kohan with [] -> [] | head::tail -> tail

C

struct node {
 void *data;
 struct node *next;
};
struct node *last (struct node *list) {
 return list->next == NULL ? list : last (list->next);
}
struct node *append (struct node *first, struct node *second) {
 if (first == NULL) {
  return NULL;
}
 last (first)->next = second;
 return first;
}
struct duplus {
 struct node *left;
 struct node *right;
};
struct duplus null_duplus = {.left = NULL, .right = NULL};
struct duplus *new_duplus (struct node *left, struct node *right) {
 struct duplus *new = malloc (sizeof (struct duplus));
 new->left = left;
 new->right = right;
 return new;
}
void del_duplus (struct duplus *ptr) {
 if (ptr != &null_duplus) {
  free (ptr);
 }
}
#define CONS(X, Y) ((X)->next = (Y))
#define HEAD(X) (X)
#define TAIL(X) ((X) != NULL ? (X)->next : NULL)
// ---------------------------------------------------------------
struct duplus *split (struct node *list, size_t i) {
 if (list == NULL) {
  return &null_duplus;
 }
 if (i < 1) {
  return new_duplus (NULL, list);
 }
 else {
  struct duplus *tmp = split (TAIL (list), i-1);
  CONS (HEAD (list), tmp->left);
  struct duplus *ret = new_duplus (list, tmp->right);
  del_duplus (tmp);
  return ret;
 }
}
struct node *remove_at (struct node *list, size_t n) {
 struct duplus *tmp = split (list, n);
 struct node *ret = append (tmp->left, TAIL (tmp->right));
 del_duplus (tmp);
 return ret;
}

　配列で処理をするのが面倒くさかったので、linked-listを使いました。
　また、C言語では'double'は予約語なので、'duplus'としました。
　このコードでは、duplusの記憶領域をsplit側で確保していますが、漏洩の可能性を減らすのならば呼び出し側で確保すべきです。
　しかし、そうするとsplitの戻り値がvoidになってしまい、何だか関数型プログラミングっぽくなくなるのでしませんでした。

感想

OCaml

　今回も分割関数splitを使いました。リストを分割することができれば、要素の挿入、削除、置換などは簡単に行えます。
　なので今回の問題は簡単でした。

C

　時間と文字数が余ったのでC言語版の答案を作成しました。C言語にしたのは、いまどきの他の言語はリスト要素の削除を標準機能で提供しているので答案にならないからです。

　二回目のC言語です。今回は、自分でリスト構造を用意したので、配列を捏ねくり回す必要がなく楽に作成できました。
　ただ、ガーベージコレクションが行われることを前提に書いているので、記憶領域の回収部分が怪しいです。

　そもそも、インテル等が56bitの残りをプログラマに自由に使わせてくれれば、タグ付きポインタをスッキリと表現でき、私のような初心者でもマークアンドスイープを簡単に実装できるはずなのです。
　なんなのでしょう「整合性の検証に使用される」と言うのは？じゃあ32bitのときはどうしてたんだYO！

　次回は、第21問です。

おまけ

　今、部屋の中に小さな甲虫が大量発生していてnoteの記事どころではありません。
　台所の小麦粉の袋が破れており、そこから湧き出ていました。
　原因を取り除いたはずなのに、まだ飛び回っています。潰しても潰しても、まだ飛び回っています。

　もしかしたら…現実には…虫など存在していないのかもしれません…あっ…また飛んでる…