PHPとJavaScriptで入れ子配列を平坦にする方法(再帰処理)

今回は [1,[4,9],16,[25,[36,49]],64] みたいな恰好をした入れ子の配列を順番をそのままで一階層の配列に直す方法を考えました。もっとスマートな関数があるようですがとりあえずは再帰処理の練習ということで、ご興味ある方はお付き合いください。言語はPHPとJavaScriptをそれぞれでやります。

1.PHPの場合

まず完成形を示します。

flatten.php

<?php
$in = [1,[4,9],16,[25,[36,49]],64];
function flat($in){
	static $i = 0;
	static $out = [];
	if(is_array($in)){
		foreach($in as $key => $val){
			flat($in[$key]);  //これが再帰(関数内で同名の関数を使う)
		}
	}elseif(is_int($in)){
		$out[$i] = $in;
		$i++;
	}
	return $out;
}
echo "<pre>";
var_dump(flat($in));　//->[1,4,9,16,25,36,49,64]
echo "</pre>";

再帰関数を使っています。つまり、関数flat内でflatを呼び出しているということです。
再帰って少し理解しやすいコツがあって、

example.php

function hoge(){
	A1; //1は第1階層
	hoge();
	B1;
}

このhoge関数内のhoge()にファンクション全体を代入すればよいのです。
なお、このexample.phpはこのままでは無限ループになります。

example.php

function hoge(){
	A1; //1は第1階層
	A2; //2は第2階層
	hoge();
	B2;
	B1;
}

どんどんやって

example.php

function hoge(){
	A1; //1は第1階層
	A2; //2は第2階層
	A3; //3は第3階層
	hoge();
	B3;
	B2;
	B1;
}

みたいになります。
A1→A2→A3と実行していって、
なんらかの条件判定などでこの第３階層で処理が終わるとすると、
その後は
B3→B2→B1
と処理されて関数が終わります。

次に注目していただきたいのは、
static宣言です。これは関数実行の際に、
最初の一回だけ実行される処理です。
つまり、再帰処理で何回もこの行は通過しますが、
もしこのstaticがないと通過するたびに初期化され
せっかく入れたデータが消えてしまいます。
ところがstaticを付けておくと初回の初期化だけで済むめっちゃ便利な宣言です。
(なお筆者の未熟の故、このstaticを使わない方法は分かりませんでした。)

そしてif文のところに来ると、まあ最初は$inは配列になっているでしょう。
そこでif(is_array($in))に引っ掛かります。

foreach($in as $key => $val){
	flat($in[$key]);  //これが再帰(関数内で同名の関数を使う)
}

が実行されます。foreachのなかでは $in[$key] は一つ上の階層の配列もしくは整数になります。

$in = [1,[2,3]];
$in[$key] → 1 or [2,3]

みたいなことですね。
直前の例で言うと1の値のようにもはや$inが配列ではなく数値になったとき、
elseif(is_int($in))が引っ掛かります。

ここで

$out[$i] = $in;
$i++;

を使って、$outという配列に添え字をインクリメントしながら、
順番に入れて、最後に第一階層のreturnで完成した$outを返します。
(恐らく第二階層以上でもreturnは実行されていますが、foreach内のhoge()では返り値を使用しておらず捨てています。)

これでめでたく平坦な配列が手に入りました。

2.JavaScriptの場合(その１)

これもまずコードを示します。これはグローバルスコープの変数i,bにアクセスしてあまりよろしくないのでその１としておきます。

flatten1.js

let i=0;
let b=[];
function flafla(arr){
	if(typeof(arr)=="object"){
		for(var j in arr){
			console.log("forward");
			console.log(arr[j]);
			flafla(arr[j]);
			console.log("backward");
			console.log(arr[j]);
		}
	}else if(typeof(arr)=="number"){
		b[i] = arr;
		i++;
	}
}
let a = [[1,2],3,[4,5,[6,7],8],[9]];

flafla(a);
console.log(b); //->[1,2,3,4,5,6,7,8,9]

これもアルゴリズム自体はPHPと同じです。
ただし、jsではstatic宣言が使えません。
よって、関数外のグローバルスコープの変数i,bに

b[i] = arr;
i++;

で無理やり成果を入れてしまうという恐ろしいことをしています。
なお、for in文内でconsole.logを書いていますが、これの挙動を把握することは非常に勉強になると思います。

3.JavaScriptの場合(その２)

さて、本命のきれいな関数です。クロージャという"関数を返す関数"を使っています。
hoge関数内かつflafla関数外のところに変数値を保持するスコープがあるわけです。
このクロージャのスコープではflafla関数内からアクセスできますが、flafla関数が終わってもhoge関数が生きているので変数値は保持されます。

flatten2.js

function hoge(){
	let i=0;
	let b=[];
	return function flafla(arr){
		if(typeof(arr)=="object"){
			for(var j in arr){
				console.log("forward");
				console.log(arr[j]);
				flafla(arr[j]);
				console.log("backward");
				console.log(arr[j]);
			}
		}else if(typeof(arr)=="number"){
			b[i] = arr;
			i++;
		}
		return b;
	}
};

let a = [[1,2],3,[4,5,[6,7],8],[9]];
console.log(hoge()(a));//->[1,2,3,4,5,6,7,8,9]

hoge関数内でflafla関数を使って、再帰になっているのです。
flafla関数が無名関数では再帰処理ができないものと思われます。
let i,bがPHPでいうstaticな値の保持をしています。
アルゴリズム的にはこれも他と同じです。
これもまた重要なのは最後の

hoge()(a)

という関数呼び出しでしょう。これはhoge()が関数flaflaを返しているので、

hoge()(a) → flafla(a)

を意味していることになります。hogeのスコープの中で変数i,bを保持しつつflaflaを実行できるなんて嬉しいですね～。（その１のflaflaに対するグローバルスコープが、このその２のflaflaに対するhogeのスコープが対応しています。）

4.おまけのJS(今までの流れぶち壊し)

flat関数というアレイメソッドがあります。
これは引数の階層分までの配列を平坦にします。
完全に平坦にするにはInfinity値を入れればよく、

const arr = [1, 2, [3, 4, [5, 6, [7, 8, [9, 10]]]]];
arr.flat(Infinity);

だけでよいです(白目)

5.最後に

アルゴリズム分かれば楽勝と思っていましたが、
言語のクセってのはあるものですね。
今日はここまで、お疲れさまでした。