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

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

問題21.

　リストの所与の位置に要素を挿入する関数insert_atを書け。

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

答案

基本的な考え方

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

本問の解き方

　以下の説明では、挿入位置を先頭からn番目とします。　
　本答案では問題17.の答案の分割関数splitを使用します。
　関数spliteを引数nに適用すると、先頭からn番目でリストが前後に分割されます。つまり、リストは挿入位置で二つに分割されます。
　そこで、これらの分割されたリストの間に挿入すべき要素を挟み込んで、それらを再結合すれば、挿入要素がn番目に位置するリストとなります。
　要素は、分割されたリストの前半部分の末尾に結合しても、後半部分の先頭に結合しても同じです。
　答案では::演算子により後半部分の先頭に結合しました。

コード

OCaml

let insert_at youso 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@youso::kohan

C

struct node {
 void *data;
 struct node *next;
};
struct node *new_node (void *data) {
 struct node *new = malloc (sizeof (struct node));
 new->data = data;
 new->next = NULL;
 return new;
}
struct node *last (struct node *list) {
 return list->next == NULL ? list : last (list->next);
}
struct node *cons (struct node *head, struct node *tail) {
 head->next = tail;
 return head;
}
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  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);
  struct duplus *ret = new_duplus (cons (HEAD (list), tmp->left), tmp->right);
  del_duplus (tmp);
  return ret;
 }
}
struct node *insert_at (struct node *list, void *element, size_t n) {
 struct duplus *tmp = split (list, n);
 struct node *ret = append (tmp->left, cons (new_node (element), tmp->right));
 del_duplus (tmp);
 return ret;
}

　リスト構造は、問題20.の答案で作成したものとほぼ同じですが、consを関数にした点と、struct nodeのコンストラクタを定義した点が異なります。

感想

OCaml

　今回の問題も簡単でした。分割関数splitが大活躍です。ここまで活躍するのなら、作成時にもう少しがんばって綺麗なコードにするべきでした。

C

　三回目のC言語です。前回の答案で折角用意したリスト構造を一度だけしか使わないのはもったいないので、今回も使うことにしました。

　C言語のコードはパターンマッチングがないのでOCamlと比べて読み易いです（驚きのOCaml全否定ですね）。
　記憶領域の回収処理のために一時変数を使用している部分が野暮ったいですが、これはガーベージコレクションを入れればもっとスッキリとするでしょう。
 　と言うことは、ガーベージコレクションを備えた「より良いC」の一つ、Javaで書けばよかったのかも知れません。次の言語が決まりましたね。

　次回は、第22問です。10月から神奈川県の最低賃金が41円も上がります。月にして6000円強も賃上げされます。今から待ち遠しくてしかたありません。