先日、mopp さんが Vim に flatten() を追加するプルリクエストを追加してくれたのだけど、その時の記憶を整理する為に書く自分の為の記事。
add flatten() to flatten list by mopp - Pull Request #3676 - vim/vim - GitHub
I'm a bit confused by the maxdepth argument. I would expect it to specify the maximum depth of the r...
https://github.com/vim/vim/pull/3676
Vim script のリストは以下の様に、異なる型が混在できる。Ruby や他のスクリプト言語でも一般的。そしてスクリプト言語には一般的にリストを平坦化する為の flatten という関数ないしはメソッドが用意されている。
let foo = [1, 2, ["bar"], 3]
Vim本体に組み込み関数を追加するパッチを投げた - Qiita
Vim本体に手を加える 次に本体への修正ですが、大体1週間くらいで出来ました。 しかし、これは私一人の力ではなく、7割りくらい vim-jp のおかげです。 vim-jpは日本のVim開発者(Plug...
https://qiita.com/mopp/items/084abe28681202bda30e
mopp さんが Advent Calendar でその時の様子を書いてくれているんだけど、flatten() ははじめ再帰を使って書かれていた。途中で僕が「ループに直したらこうなる」という感じにコードを貼ってしまったので、後でループに直す実装を楽しみにしていた mopp さんには悪い事をしてしまった。申し訳ない。ぜひ次は flat_map() を実装して下さい。その時考えていたのだけど、flatten() の様な関数を再帰でなくループにするには本来ならばスタックに相当する何かが必要になるはずだろうと踏んでいた。なぜならリストを再帰降下するという事は戻り場所を知っておく必要があり、ループに直すのであればそれ相当のスタック配列が必要だと考えていたからだ。そして一般的にはこのスタック配列の実装がめんどくさいので皆再帰を使ってお茶を濁そうとする。僕もよくやる。
例えば以下の様な簡単なリスト構造を作ってみたとする。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef enum _type_t {
INT_T,
STRING_T,
LIST_T,
} type_t;
typedef struct _value_t {
int ref;
type_t type;
union {
int n;
char *s;
struct _list_t *l;
} val;
} value_t;
typedef struct _item_t {
struct _item_t *next;
value_t *value;
} item_t;
typedef struct _list_t {
item_t *first;
} list_t;
static void
free_value(value_t *v) {
item_t *i;
if (v->ref-- > 0) return;
switch (v->type) {
case INT_T:
break;
case STRING_T:
free((void*)v->val.s);
break;
case LIST_T:
i = v->val.l->first;
while (i != NULL) {
item_t *next = i->next;
free_value(i->value);
free(i);
i = next;
}
free((void*)v->val.l);
break;
}
free((void*)v);
}
static value_t*
new_list_value() {
value_t *v = malloc(sizeof(value_t));
v->type = LIST_T;
v->val.l = malloc(sizeof(list_t));
v->val.l->first = NULL;
v->ref = 0;
return v;
}
item_t*
new_item(value_t *v) {
item_t *item = malloc(sizeof(item_t));
item->value = v;
item->next = NULL;
++v->ref;
return item;
}
static void
list_add_value(list_t *list, value_t *rhs) {
item_t *i = list->first;
if (i == NULL) {
list->first= new_item(rhs);
return;
}
while (i->next != NULL) {
i = i->next;
}
i->next= new_item(rhs);
}
static void
list_insert_value(list_t *list, item_t *before, value_t *value) {
item_t *next;
if (before == NULL) {
list->first= new_item(value);
return;
}
next = before->next;
before->next= new_item(value);
before->next->next = next;
}
static void
list_remove_item(list_t *list, item_t *item) {
item_t *i, *before = NULL;
for (i = list->first; i != NULL; i = i->next) {
if (i == item) {
if (before == NULL)
list->first = i->next;
else
before->next = i->next;
free_value(item->value);
free(item);
return;
}
before = i;
}
}
static value_t*
new_int_value(int n) {
value_t *v = malloc(sizeof(value_t));
v->type = INT_T;
v->val.n = n;
v->ref = 0;
return v;
}
static value_t*
new_string_value(const char* s) {
value_t *v = malloc(sizeof(value_t));
v->type = STRING_T;
v->val.s = strdup(s);
v->ref = 0;
return v;
}
static void
print_value(value_t *v) {
item_t *i;
switch (v->type) {
case INT_T:
printf("%d", v->val.n);
break;
case STRING_T:
/* TODO: escape non-printable */
printf("\"%s\"", v->val.s);
break;
case LIST_T:
printf("[");
for (i = v->val.l->first; i != NULL; i = i->next) {
print_value(i->value);
if (i->next) printf(", ");
}
printf("]");
break;
}
}
int
main(int argc, char* argv[]) {
value_t *list, *sub;
list = new_list_value();
list_add_value(list->val.l, new_int_value(1));
list_add_value(list->val.l, new_string_value("foo"));
sub = new_list_value();
list_add_value(sub->val.l, new_string_value("bar"));
list_add_value(list->val.l, sub);
list_add_value(list->val.l, new_int_value(3));
print_value(list);
free_value(list);
return 0;
}
数値と文字列とリストが扱える物。リストの中にはそのいずれかを混入できる。お気持ち程度の参照カウンタを入れてあるが動くかどうか確認してないし本題はそこじゃない。これを実行すると以下の様に表示される。
[1, "foo", ["bar"], 3]
このリスト関数を使って flatten() を実装する場合、簡単に思い付くのが再帰を使った以下の方法。vital.vim でも再帰を使ってる。
function! s:flatten(list, ...) abort
let limit = a:0 > 0 ? a:1 : -1
let memo = []
if limit == 0
return a:list
endif
let limit -= 1
for Value in a:list
let memo +=
\ type(Value) == type([]) ?
\ s:flatten(Value, limit) :
\ [Value]
unlet! Value
endfor
return memo
endfunction
上記のリスト関数を使った場合だと以下の様になる。
static void
flatten_list(item_t *before, list_t *list) {
item_t *i, *j, *prev = NULL;
for (i = list->first; i != NULL; i = i->next) {
if (i->value->type == LIST_T) {
flatten_list(i, i->value->val.l);
list_remove_item(list, i);
return;
}
if (before != NULL) {
list_insert_value(list, before, i->value);
before = before->next;
}
}
}
リストを舐めながら要素がリストだったら挿入位置とそのリストを引数に要素を追加する関数(自身)を呼び出す。呼び出したあと元々リストがあった箇所を削除する。この flatten() は再帰を使ってるのでメモリを多く消費するしスタックオーバーフローで突然死してしまう可能性がある。でも良く考えると flatten() は、現在いる要素の子要素がリストの場合、そのリストの中身をすべて現在いる場所に移動し、自身を削除し、そして今と同じ箇所で再検査すればいいだけなのだ。スタックとして覚えておく必要もない。なので実装は以下の様になる。
static void
flatten_list(list_t *list) {
item_t *i, *j, *prev = NULL;
for (i = list->first; i != NULL; i = i->next) {
if (i->value->type == LIST_T) {
item_t *before = i;
for (j = i->value->val.l->first; j != NULL; j = j->next) {
list_insert_value(list, before, j->value);
before = before->next;
}
if (prev == NULL)
list->first = i->next;
prev->next = i->next;
i = prev;
}
prev = i;
}
}
言ってみるならば、自分がネストに降下するんじゃなく、flat にする事でネストがこっちに上がってくるという事。実行すると以下が表示される。
[1, "foo", "bar", 3]
再帰は消え、スタックオーバーフローの心配もなくなり、メモリの消費量も減り、良い事づくめだ。逆に、今まで何度か flatten() は書いた事があるけどなぜ自分はこれまで flatten() を再帰で作ろうと考えてしまったのかと思い起こしたくもなった。
追記 この最適化方は自身のリストが破壊されるから出来る方法なので、flatten 済みのリストをを返す場合には使えないので注意。
