変な引き算と入れ子配列の平坦化、TypeScriptで - 檜山正幸のキマイラ飼育記 (はてなBlog)

変な引き算

自然数（0を含む）の範囲内だけで考えます。7 - 5 は2です、では 3 - 5 は？自然数の範囲で 3 - 5 の引き算は出来ません。未定義とするのがひとつの案です。どうしても何か値を出せと言われたら、しょうがないので0とするのもアリです。引けないときは0にしちゃう引き算はたまに使われることがあります*1。

もうひとつ別な方法として、引けないときは元の数（左側）をそのまま答にしてしまう演算を考えます。3 - 5 = 3 です。普通の引き算とは違うので、「-/」という演算子記号を使うことにしましょう。

7 -/ 5 = 2
3 -/ 5 = 3
10 -/ 9 = 1
9 -/ 10 = 9
0 -/ 1 = 0

整数の割り算をするとき、商と余りが一度に出ると便利です。この変な引き算も多値だとして、普通に引けたときは1、引けなかったときは0というフラグを一緒に出力することにします。多値の変な引き算は次のようになります。

7 -/ 5 = [1, 2]
3 -/ 5 = [0, 3]
10 -/ 9 = [1, 1]
9 -/ 10 = [0, 9]
0 -/ 1 = [0, 0]

n -/ m = [k, j] のとき、n = m×k + j が成立します。

もっと変な引き算

変な引き算「-/」の右側に、自然数の配列（リスト）を許すとします。例えば、10 -/ [3, 1, 5] とかです。これは、基本的には変な引き算の繰り返しです。10 -/ [3, 1, 5] は、((10 -/ 3) -/ 1) -/ 5 のことです。引けるのであれば普通に引き算して、無理なら左の数をそのまま出力します。

((10 -/ 3) -/ 1) -/ 5 は普通に引き算が出来るので、答は1です。今まで0,1のフラグだった値は、引き算が何回出来たかを示すカウンターに変えます。今の例では、普通の引き算が3度出来たので、10 -/ [3, 1, 5] = [3, 1] となります。n -/ [m] は、n -/ m と同じになります。

今説明した、右側が配列になる変な引き算をTypeScriptで書いてみます。

// 自然数型をうまく定義できないので、ナンチャッテ定義
// naturalはintegerで0以上
type natural = number;

function subtractStrangely(n:natural, a:Array<natural>) : [natural, natural] {
  var k:natural = 0;
  var j:natural = n;
  for (var i = 0; i < a.length; i++) {
    var m = a[i];
    if (j >= m) {
      // 引き算ができる
      k++;
      j -= m;
    } else {
      // 引き算ができない
      break;
    }
  }
  return [k, j]; // 多値を配列として返す
}

入れ子配列の平坦化

入れ子になった配列（リスト）を平坦化する関数は例えば次のように書けるでしょう。

function flatten<X>(aax: Array<Array<X>>) : Array<X> {
  var result:Array<X> = [];
  // ディープコピーはしない（さぼり）
  aax.forEach(
    (ax:Array<X>)=>
      ax.forEach( (item:X)=>result.push(item) )  
  )
  return result;
}



> flatten([[1,2], [3, 4, 5]])

  [1, 2, 3, 4, 5]

flatten関数は、配列データをガチャガチャと操作して平坦化した配列を作り出しています。ガチャガチャ操作をしないで平坦化できないでしょうか。

元のデータ（入れ子の配列）には一切手を加えないでも、インデックス・アクセス要求時に、あたかも平坦化したように振る舞えば充分です。インデックス・アクセスの演算子であるブラケット（[]）をオーバーロードできるといいのですが、TypeScriptでは無理みたいなので、itemというメソッドを使うことにします。

class Flattened<X> {
  private data: Array<Array<X>>;
  private lengths: Array<natural>;
  length: natural;
  constructor(aax: Array<Array<X>>) {
    // ディープコピーはしない（さぼり）
    this.data = aax; // 元のデータそのもの
    this.lengths = aax.map((ax:Array<X>)=>ax.length);
    this.length = this.lengths.reduce((acc:natural, val:natural)=>acc+val, 0);
  }
  
  item(n:natural) : X {
    if (this.length <= n) {
      return undefined;
    }
    var r:[natural, natural] = subtractStrangely(n, this.lengths);
    var k = r[0], j = r[1];
    return this.data[k][j];
  }
}

function flattenStrangely<X>(aax: Array<Array<X>>) : Flattened<X> {
  return new Flattened<X>(aax);
}

インデックス・アクセス item(n) を、内部的に this.data[k][j] に変換するときに、配列に関する変な引き算（subtractStrangely関数）を使っています。

長さ（length）とインデックス・アクセス（[]またはitem）だけを観測するなら、flatten関数でもflattenStrangelyでも同じであることは次のようなテストで確認できます。同じ演算子記号[]が使えると、もっと区別できなかったんですけどね、ちょっと残念。

function tester<X>(aax: Array<Array<X>>) : boolean {
  var flattened1 = flatten(aax);
  var flattened2 = flattenStrangely(aax);
  if (flattened1.length !== flattened2.length) {
    return false;
  }
  for (var i = 0; i < flattened1.length; i++) {
    // 型Xはスカラーで、
    // 配列の要素は === で比較可能だとする（さぼり）
    if (flattened1[i] !== flattened2.item(i)) {
      return false;
    }
  }
  return true;
}

あ、それと； var [k, j] = subtractStrangely(n, this.lengths); って書き方、できなかったんだっけ？＞TypeScript、それも残念。

*1:この引き算については、近藤基吉先生に教えてもらったことがあります。制限差と呼び、点を添えたマイナスで表します。