JavaScriptの概念 (後半)

「[JavaScriptの概念 (前半)](https://qiita.com/_linkin/items/8f1889957e6d695fc539)」の続きです。

## 11. Prototype Chain
JavaScriptには2つの特徴があります。1つは「全てがオブジェクト」もう１つは「prototypeベースの言語」です。
```js
const foo = {
  a: "foobar"
};
console.log(foo instanceof Object);    // -> true

const bar = [1, 2, 3];
console.log(bar instanceof Object);    // -> true

const piyo = new Map([[1, 'one'], [2, 'two']]);
console.log(piyo instanceof Object);    // -> true
```
配列やMapも全部、内部的にはオブジェクトですね。

全てのオブジェクトには`prototype`というプロパティが存在しています。日本語に訳すと「原型」。この`prototype`が`class`の継承のような役割を果たします。

`prototype`の役割を明らかにするために少し詳しく。
```js
// Arrayのprototypeにfooメソッドを定義すると...
Array.prototype.foo = function(){
  console.log(this);
}

const baz = [1, 2, 3];
// 全てのArrayから呼び出せるようになる
baz.foo();     // -> [1, 2, 3]
```
`baz`に`foo()`メソッドを定義していなかったにも関わらず`foo()`が呼び出せてしまいます。これが`prototype`の力です。

配列`baz`を定義し、同時に`foo.__proto__`という内部プロパティに`Array.prototype`への参照がセットされます。そして`baz.foo()`が呼び出されるとまず`baz`自身のプロパティに`foo`が存在するかが確認され、なければ次に`baz.__proto__.foo`が存在するかを確認します。今回は`baz.__proto__.foo()`が実行されたというわけです。

同じように`Object.prototype.foo`を定義してみます。
```js
Object.prototype.foo = function(){
  console.log(this);
}

const baz = [1, 2, 3];
baz.foo();     // -> [1, 2, 3]

const bar = new Map([[1, 'one'], [2, 'two']]);
bar.foo();     // -> Map(2) {1 => "one", 2 => "two"}
```
今度は`baz.__proto__.foo`が存在しません。すると次に`baz.__proto__.__proto__.foo`を確認します。このように、**呼び出したメソッドが存在しなければ見つかるまで親の`prototype`をさかのぼり続けます**。これがprototypeチェーンの仕組みです。

ArrayもMapもオブジェクトの子供なのでprototypeチェーンをさかのぼった結果Object.prototype.hogeが実行されたというわけです。

もっとも、今はclass構文があるのでprototypeを直接触るようなコードを書くことはほぼ無いと思います。

#### コラム：ラッパーオブジェクト
JavaScriptは全てがオブジェクトという話の例に配列やMapをあげたのですが、実は**プリミティブな文字列などもオブジェクトのように扱うことができます**。
```js
console.log(true.toString());       // -> "true"
console.log('foo'.toUpperCase());  // -> "FOO"
```
これはプリミティブの要素にアクセスしようとすると**内部的にラッパーオブジェクトに自動で変換される**ためです。`true.toString()`は実際には`new Boolean(true).toString`のように処理されます。

この辺りの変換は自動でやってくれるので深く考える必要はありません。わざわざnew Boolean()などを書く必要はないということだけ覚えておけば良いでしょう。

## 12. Object.create & Object.assign
Object.createは`prototype`オブジェクトの継承を行うために使用されます。`class`構文と同等のことが関数で実行できるというわけですね。

例えばFooを継承したBazを書く場合は以下のようになります。
```js
function Foo(){
  this.name = 'NoName';
}
Foo.prototype.sayHello = function(){
  return `Hello! I am ${this.name}!`;
}

function Baz(){
  Foo.call(this);  // class構文ではsuper()を使う
}
Baz.prototype = Object.create(Foo.prototype);
Baz.prototype.constructor = Baz;

const baz = new Baz();
console.log(baz.sayHello());   // -> "Hello! I am NoName!"
```
Object.assignは複数のオブジェクトを結合してくれる関数です。
`prototype`を結合して多重継承(mixin)のように使用したり、第一引数を`{}`にしてオブジェクトをコピーする用途で多用されていました。今はスプレッド演算子を使用します。
```js
const obj1 = { foo: 'foo' };
const obj2 = obj1   // これだと同じインスタンスを共有してしまう
const obj3 = Object.assign({}, obj1);   // 新しいオブジェクトを作成し、それにobj1の内容をコピーする
const obj4 = {...obj1}; // 今はスプレッド演算子を使う

obj1.foo = 'baz';

console.log(obj1.foo); // -> "baz"
console.log(obj2.foo); // -> "baz"
console.log(obj3.foo); // -> "foo"
console.log(obj4.foo); // -> "foo"
```

## 13. Array.prototypeの便利な関数たち
`Array.prototype`には配列操作のための便利な関数が色々用意されています。`prototype`にある関数はどのArrayオブジェクトからでも呼び出せます。

### 配列をスタックやキューのように使う
**スタックとはLIFO(後入れ先出し)型のデータ格納方式**です。コールスタックもスタックの一種で、後から入った関数が先に処理されていましたね。

配列をスタックのように使用するには`push()`と`pop()`を使用します。
```js
const stack = [];
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack);         // -> [1, 2, 3]

while( stack.length > 0 ){
  console.log(stack.pop()); // -> 3  2  1
}                           // 後ろから出てくる
```
**キューはFIFO(先入れ先出し)型のデータ格納方式**です。こっちは`push()`と`shift()`を使用します。
```js
const queue = [];
queue.push(1);
queue.push(2);
queue.push(3);
console.log(queue);             // -> [1, 2, 3]

while( queue.length > 0 ){
  console.log(queue.shift());   // -> 1  2  3
}                               // 前から出てくる
```
`push()`は配列の後ろに新しい要素を突っ込んでくれる関数でしたが、配列の前に要素を突っ込むための`unshift()`という関数もあります。

### sort
配列をソートしたい場合は`sort()`という関数を使用します。ただし若干動作に癖があって、全ての要素は内部的にStringに変換され、辞書順でソートされてしまいます。
```js
const arr = [1, 10, 5, 30];
arr.sort();             // 引数無しの場合"1", "10", "5", "30"が辞書順になるようにソートされる
console.log(arr);       // -> [1, 10, 30, 5] (元の型がStringに変換される訳では無い)

arr.sort( (a,b) => (a-b) ); // 数字の大小などでソートする場合は自分で比較関数を書く
console.log(arr);       // -> [1, 5, 10, 30]
```

比較関数をうまく使うことでオブジェクトのソートなどを自由に行うことができます。
```js
const items = [
  { name: 'watace', value: 100 },
  { name: 'foo', value: 90 },
  { name: 'bar', value: 110}
];

// nameの辞書順でソート
items.sort( (a,b) => {
  if(a.name < b.name) return -1; // 負の数字が返ってこればa<bと判定される
  if(a.name > b.name) return 1;  // 正の数字だとa>bと判定される
  return 0; // 0の場合の順序は保証されない
});
console.log(items);     
// -> [{name: "bar", value: 110}, {name: "foo", value: 90}, {name: "watace", value: 100}]

// valueの大小でソート
items.sort( ( a, b ) => ( a.value - b.value ) );
console.log(items);
// -> [{name: "foo", value: 90}, {name: "watace", value: 100}, {name: "bar", value: 110}]
```

#### コラム：関数型プログラミング
関数型プログラミングとはどういうものなのかについて簡単に説明します。正確性に欠けますが、関数型プログラミングは **「関数とデータを引き離す」プログラミング手法** のことです。

- 関数が関数外部の状態を変化させない
- 関数が引数以外の入力を受け取らない

数学の関数みたいに考えるとわかりやすいかもしれません。例えばf(x)=2x+3みたいな感じである入力xに対してどのような出力をするのかを定義します。似たような感じでg(x)=-3xみたいに定義すると、下のように数学的に記述できるんですね。
```js
const f = x => 2*x + 3;
const g = x => -3*x;

const x = 3;    // 入力データ

const data = g(f(x));
console.log(data);  // -> -27

// 何回同じ処理をしても入力が同じなので出力は変化しない
console.log(g(f(x)));   // -> -27
console.log(g(f(x)));   // -> -27
```
**元の関数を変化させず、同じ入力をすれば何度操作を繰り返しても同じ出力が得られます**。

関数型プログラミングの概念をもとにコードを組んでいくと、処理の途中でデータが変化することがなくなるのですが、それを「サイドエフェクトがない」だとか「純粋関数」だとか言うわけです。早速見ていきましょう。


## 14. サイドエフェクトと純粋関数
関数は入出力のルートをそれぞれ2つずつ持っています。
```js
const hiddenInput = 5;
const obviousInput = 3;
let hiddenOutput;
let obviousOutput;

const func = x => {
  // 隠れた入出力を持つ
  hiddenOutput = x * hiddenInput;
  return x;
};

obviousOutput = func( obviousInput );
```
関数が隠れた出力を持つ場合、その関数には **「サイドエフェクト(副作用)がある」** と言い、隠れた入力を持つ場合は **「参照透過性がない」** と言います。

### サイドエフェクト(副作用)
サイドエフェクトとは日本語でいうと「副作用」のことで、関数を実行した際に何らかの状態を変化させてしまう場合に「サイドエフェクトがある」というように使用します。

```js
// サイドエフェクトを持つ関数
let a = 0;
const inc = () => {
  a += 1;
};

// サイドエフェクトを持たない関数
const inc = a => a + 1;
```

基本的に **「関数を実行した際に何が起きるのかがその行だけで明白」** にできるように気をつけていれば自然とサイドエフェクトが無いコードが書けると思います。

```js
// サイドエフェクトを持つ場合
let a = 0;
inc();  // 何が起きているのかパッと見では分からない
inc();
console.log(a); // -> 2

// サイドエフェクトを持たない場合
let a = 0;
a = inc(a);
a = inc(a);
console.log(a); // -> 2
```
#### コラム：組み込みオブジェクトの独自拡張

どうせならパイプ記法的に`const b = a.inc().inc();`みたいに書く。
そういう場合はサクッと新しいクラスを作る。
```js
class ExNumber extends Number{
  constructor(args){
    super(args);
  }
  inc(){
    return new ExNumber( this + 1 );
  }
}

const foo = new ExNumber(1);
console.log(foo);  // -> 1
const bar = foo.inc().inc().inc();
console.log(bar);  // -> 4
console.log(foo);  // -> 1
```

### 参照透過性
参照透過性をもつ関数とは隠れた入力を持たない関数のことで、簡単にいってしまえば **「同じ引数で実行すれば必ず同じ返り値になる関数」** です。

### 純粋関数
純粋関数とは、関数のうち **「サイドエフェクトが無い」かつ「参照透過性をもつ」** もののことをさします。

外部の状態とは完全に独立しているので、コードを解読する際に考えないといけないことが減ります。状態から独立しているので並列処理にも強いです。
```js
// 純粋な例
const addPerson = (group, person) => {
  return [...group, person];
}

const group1 = [];
const group2 = addPerson(group1, { name: 'foo' });
console.log(group1);    // -> []
console.log(group2);    // -> [{name: "hoge"}]

// 純粋でない例
const addPerson = (group, person) => {
  group.push(person);
}
const group = [];
addPerson(group, { name: 'foo' });
```
ネストされたオブジェクトは適当に処理してると参照コピーになるので注意です。

## 15. クロージャー
関数が**外側のスコープにある変数への参照を保持できる**ようになっています。この性質のことを「クロージャー」と呼び、これを利用すると関数にあたかも状態を持つかのような挙動をさせることができます。
```js
const createCounter = () => {
  let cnt = 0;
  return {
    inc: () => ++cnt
  }
};

const counter = createCounter();

console.log(counter.inc()); // -> 1
console.log(counter.inc()); // -> 2

// 当然ですが、counterはただの関数です。cntにはアクセスできません。
console.log(cnt); // -> ReferenceError
console.log(counter.cnt); // -> undefined
```
JavaScriptでは不要になったメモリをガベージコレクタが自動で解放してくれるのですが、その解放基準は **「グローバルオブジェクトから到達できるかどうか」** となっています。

上記の例では`global -> counter -> cnt`と参照されているため、cntのメモリが解放されずに内部状態のように働いています。

## 16. 高級関数
関数を引数にしたり戻り値を関数にすることができます。`sort()` `map()` `filter()` `reduce()` は全て引数に関数をとるので高階関数だと言えます。また、クロージャーなどで関数を返すものも高階関数だと言えるでしょう。

## 17. 再帰(HOF)
再帰の例といえば`5!`みたいな階乗ですよね。
```js
const foo = condition => {
  if (condition) {
    return bar;
  } else {
    return baz;
  }
};
// ↕︎同じ
const foo2 = condition => condition ? bar : baz;
```

## 18. データ構造
データ構造とはデータの集まりを**どのような形式で格納するのか**というものです。データ構造次第でどのような処理が得意なのかが決まってくるため、特に処理すべきデータが多い場合には目的に沿って適切なデータ構造を選択する必要があります。

### 配列
連続したメモリアドレス上にデータを格納する構造。それぞれのデータへのアクセスがO(1)で行える。データの挿入・削除はO(n)。データの探索も基本的にはO(n)になる。
※JavaScriptの配列の実装はこの配列とは異なる場合があるので注意。

### 連想配列
配列はa[0]みたいに数字を添字にしてアクセスするんですが、**数字以外の型でアクセスできる**ようにしたものが連想配列です。JavaScriptは全てのオブジェクトがこの連想配列になっています。JavaScriptでの実装ではそれぞれのデータへのアクセスやキーの追加・削除などがO(1)で行えます。

### リスト
**データと「別のデータへのポインタ」を保持するデータ構造**。配列に比べると任意の位置での挿入・削除がO(1)でできるというのがメリット。ただしランダムアクセス性は低い。

- 片方向リスト
後ろしか指さないタイプのリスト。逆に辿ることはできない。

- 双方向リスト
両方指すタイプのリスト

など。

### グラフ
頂点と枝からなるデータ構造。

### 木
閉路を持たず、全ての頂点が連結されているグラフのこと。例えばDOMはツリーとしてメモリ上に展開されています。

## 19. カリー化と部分最適

### カリー化
**全ての関数の引数の数を1つにする**ことだと言えます。
```js
// カリー化されていない
const add = (a, b) => a + b;
console.log(add(1, 2));     // -> 3

// カリー化されている
const ExAdd = a => b => a + b;
console.log(cAdd(1)(2));    // -> 3
```
関数を受け取ってカリー化するための関数を自前で実装すると下のようになります。
以下は、元関数の引数が2個の時のものです。
```js
const curry = fn => (
  function Exfn(a, b) {
    switch (arguments.length) {
    case 0:
      return Exfn;
    case 1:
      return _b => fn(a, _b);
    default:
      return fn(a, b);
    }
});

const add = (a, b) => a+b;
const ExAdd = curry(add);

console.log(ExAdd());        // -> function Exfn(a, b){...}
console.log(ExAdd(1));       // -> _b => add(1, _b)
console.log(ExAdd(1)(2));    // -> 3
console.log(ExcAdd(1, 2));    // -> 3
```

### 部分最適
関数がカリー化されている場合に使用できるテクニックが「部分適用」です。ほぼ確実にカリー化とセットで登場します。部分適用とは **「元々の関数の引数の一部を固定する」** というもので、前節の例でいうと下記の部分が部分適用です。
```js
// add()の第一引数が1に固定されている
console.log(ExAdd(1));       // -> _b => add(1, _b)
```

## 最後に
これも身に染みたら削除します。