遅延シーケンスを用いた無限素数列 in JavaScript
で使っている遅延連結リストの動作原理とそれを理解
するために必要な前提知識の再確認および演習です.

function と =>

「function」で関数を定義する場合と「=>」で関数を定義する場合で

	function	=>
prototype	使える	使えない
名前を使った再帰	使える	使えない
new で呼び出してコンストラクタとして	使える	使えない

のような違いがあります.

上記機能と無関係なものは「=>」を使い,
本記事では, 上記機能を使いたい場合は「function」を使っていきます.
(function を使わない版はこちら )

基本的には各式の評価結果は掲載しないので,
各自手元の環境で評価させ, 確認してください.

この記事のコードの動作確認に使った実行環境は Node.js v19.5.0 です.

再帰呼出し (Recursive Call) の再確認

関数リテラル

階乗を例にします.

function f (n) { return (n == 0)?1:n*f(n - 1) } のように
定義中の関数の名前を定義の中で使って再帰できます.

上記の関数を 5 を引数として即時実行し, 5 の階乗を得ます.

(function f (n) { return (n == 0)?1:n*f(n - 1) })(5)

この時 f はリテラルの中で使われるだけで, グローバルな名前を消費していないことに注意してください.

f(5)
// => Uncaught ReferenceError: f is not defined

関数リテラルを変数に代入

関数に名前をつけてもよいです.

関数リテラルを変数に代入する方法と function 文で宣言同時定義する方法があります.

関数リテラルを変数に代入

const factorial = function f (n) { return (n == 0)?1:n*f(n - 1) }

動作確認

factorial(5)
[3,1,4,1,5,9,2,6].map(factorial)

この時 f はグローバルスコープの名前を消費していないことを再度確認

f(5)
// => Uncaught ReferenceError: f is not defined

function 文で宣言同時定義

function factorial2 (n) {
  return (n == 0)?1:n*factorial2(n - 1)
}

動作確認

factorial2(5)
[3,1,4,1,5,9,2,6].map(factorial2)

連結リスト (Linked List)

定義

連結リストを実装する方法は, いくつか考えられますが,
ここでは配列を使っていきます.

const cons = (a, b) => [a, b]
const car = l => l[0]
const cdr = l => l[1]

cons(a, b) : 第二引数で指定した連結リスト b の先頭に第一引数 a を連結した連結リストを返します.
car(l) : 連結リスト l の先頭の要素を返します.
cdr(l) : 連結リスト l の二番目以後の要素からなる連結リストを返します.

リストの終端は null を使うものとします.

サンプル

サンプルの数字リスト

const snl = cons(3, cons(1, cons(4, cons(1, cons(5, cons(9, cons(2, cons(6, null))))))))

サンプルの単語リスト

const swl = cons('May', cons('I', cons('have', cons('a', cons('large', cons('container', cons('of', cons('coffee', null))))))))

連結リストと再帰呼出しは相性が良いので,
再帰呼出しを使えば連結リストに対して reduce 処理ができます.

(reduce って何? という方はこちらの記事をどうぞ)

動作確認

数値列の要素の総和

(function f(l) { return (l == null)?0:(car(l) + f(cdr(l))) })(snl)

数値列の要素の総積

(function f(l) { return (l == null)?1:(car(l) * f(cdr(l))) })(snl)

数値列の要素の最大値

(function f (l, a) {
  return (a == null)?f(cdr(l), car(l)):(
           (l == null)?a:(
             (a < car(l))?f(cdr(l), car(l)):f(cdr(l), a)
           )
         )
})(snl)

単語列の要素の最長単語

(function f (l, a) {
  return (a == null)?f(cdr(l), car(l)):(
           (l == null)?a:(
             (a.length < car(l).length)?f(cdr(l), car(l)):f(cdr(l), a)
           )
         )
})(snl)

reduce の実装

reduce 相当の処理を毎回書くのではなく reduce を実装します.

function reduce(l, f, a) {
  return (a == null)?reduce(cdr(l), f, car(l)):(
           (l == null)?a:reduce(cdr(l), f, f(a, car(l)))
         )
}

すると先に例で出した処理は定義した reduce を使って記述できます.

reduce(snl, (a, x) => a + x, 0)
reduce(snl, (a, x) => a * x, 1)
reduce(snl, (a, x) => (a < x)?x:a)
reduce(snl, (a, x) => (a.length < x.length)?x:a)

配列を連結リストに変換する関数を reduce (配列のメソッドであり, 先ほど定義した reduce ではありません) を使って実装します.

const array2list = ar => ar.reverse().reduce((a, x) => cons(x, a), null)

すると先の snl, swl と同じ連結リストを以下のように作ることができます.

const snl2 = array2list([3,1,4,1,5,9,2,6])
const swl2 = array2list(['May', 'I', 'have', 'a', 'large', 'container', 'of', 'coffee'])

以下で動作確認をしてみてください.

reduce(snl2, (a, x) => a + x, 0)
reduce(snl2, (a, x) => a * x, 1)
reduce(snl2, (a, x) => (a < x)?x:a)
reduce(swl2, (a, x) => (a.length < x.length)?x:a)

演習

配列のメソッド map に相当する処理を上記で定義した連結リストに
対して行う関数を実装してください.
定義した map に上記サンプル数値列と適当な関数リテラルを与え,
数値列の各要素を二乗した数値列を返す処理を記述し, 動作確認してください.
定義した map に上記サンプル単語列と適当な関数リテラルを与え,
単語列の各要素を, その単語の末尾にその単語の頭尾を反転した単
語を連結した単語に変換 (May を MayyaM に変換) する処理を記述
し, 動作確認してください.

prototype を使ったインスタンスメソッド

(以下のコード例はここまでの定義をクリアして実行してください)

連結リストの定義を変更

prototype を使い, 連結リストのメソッドとして
car, cdr, reduce を使えるようにします.

連結リストの実装は以下に変更します.

function LinkedList (a, b) {
  this.car = () => a
  this.cdr = () => b
}
const cons = (a, b) => new LinkedList(a, b)

cons(a, b) : 第二引数で指定した連結リスト b の先頭に第一引数 a を連結した連結リストを返します.
l.car() : 連結リスト l の先頭の要素を返します.
l.cdr() : 連結リスト l の二番目以後の要素からなる連結リストを返します.

リストの終端は cons(null, null) を使うものとします.

サンプル

例によって, サンプルの数字リストと単語リストを作っておきます.

const snl = cons(3, cons(1, cons(4, cons(1, cons(5, cons(9, cons(2, cons(6, cons(null, null)))))))))
const swl = cons('May', cons('I', cons('have', cons('a', cons('large', cons('container', cons('of', cons('coffee', cons(null, null)))))))))

prototype を使って LinkedListのインスタンス.reduce(関数, 初期値) のように
reduce を呼べるようにします.

LinkedList.prototype.reduce = function (f, a) {
  return (a == null)?this.cdr().reduce(f, this.car()):(
    (this.car() == null)?a:this.cdr().reduce(f, f(a, this.car()))
  )
}

動作確認

snl.reduce((a, x) => a + x, 0)
snl.reduce((a, x) => a * x, 1)
snl.reduce((a, x) => (a < x)?x:a)
swl.reduce((a, x) => (a.length < x.length)?x:a)

遅延連結リスト (Lazy Linked List)

(以下のコード例はここまでの定義をクリアして実行してください)

定義

連結リストの次の要素を指す部分は, 次の要素を返す関数, を指定するものとし,
取り出すときは, 格納されている関数を実行するものとします.

function LazyLinkedList (a, b) {
  this.car = () => a
  this.cdr = b
}
const cons = (a, b) => new LazyLinkedList(a, b)

cons(a, b) : 第二引数で指定した遅延連結リストを返す関数 b の先頭に,
第一引数 a を連結した遅延連結リストを返します.
l.car() : 遅延連結リスト l の先頭の要素を返します.
l.cdr() : 遅延連結リスト l の二番目以後の要素からなる遅延連結リストを返します.

リストの終端は cons(null, () => null) を使うものとします.

サンプル

例によって, サンプルの数字リストと単語リストを作っておきます.

const snl =
  cons(3, () =>
    cons(1, () =>
      cons(4, () =>
        cons(1, () =>
          cons(5, () =>
            cons(9, () =>
              cons(2, () =>
                cons(6, () =>
                  cons(null, () =>
                    null)))))))))
const swl =
  cons('May',       () =>
    cons('I',         () =>
      cons('have',      () =>
        cons('a',         () =>
          cons('large',     () =>
            cons('container', () =>
              cons('of',        () =>
                cons('coffee',    () =>
                  cons(null,        () =>
                    null)))))))))

基本動作の確認

reduce, toString を実装し,
数値列の総和, 総積, 最大値, 単語列の最長単語の例が機能するか,
文字列化が機能するか, 動作確認をします.

LazyLinkedList.prototype.reduce = function (f, a) {
  return (a == null)?this.cdr().reduce(f, this.car()):(
           (this.car() == null)?a:this.cdr().reduce(f, f(a, this.car())))
}

snl.reduce((a, x) => a + x, 0)
snl.reduce((a, x) => a * x, 1)
snl.reduce((a, x) => (a < x)?x:a)
swl.reduce((a, x) => (a.length < x.length)?x:a)

LazyLinkedList.prototype.toString = function (f) {
  return (this.car() == null)?"":(this.car() + ", " + this.cdr().toString())
}

snl.toString()
swl.toString()

遅延連結リストを使った無限シーケンス

無限シーケンスの例として自然数列を遅延連結リストを使って定義します.

const nns = (function f(n) {
  return cons(n, () => f(n + 1))
})(1)

定義する時に「いくつまでの自然数」という情報が入らず,
使う時に, いくつまで使うかが指定できることが重要です.

最初の数個の要素を確認してみます.

nns.car()
nns.cdr().car()
nns.cdr().cdr().car()

先頭から指定した個数までの要素からなる遅延連結リストを返すメソッド take を実装し,
自然数列で動作確認をします.

LazyLinkedList.prototype.take = function (n) {
  return (n == 0)
    ? cons(null, () => null)
    : cons(this.car(), () => this.cdr().take(n - 1))
}

nns.take(10).toString()
nns.take(100).toString()

先頭から指定した個数を要素を取り除いた遅延連結リストを返すメソッド drop を実装しますが,

LazyLinkedList.prototype.dropBeauty = function (n) {
  return (n == 0)
    ? this
    : this.cdr().dropBeauty(n - 1)
}

のように実装すると再帰構造で記述できて美しいのですが,

nns.dropBeauty(10).car()
nns.dropBeauty(100).car()
nns.dropBeauty(1000).car()
nns.dropBeauty(10000).car()

と増やしていった場合に, スタックオーバーフローを起こします.
手元の環境では

nns.dropBeauty(100000).car()
// => Uncaught RangeError: Maximum call stack size exceeded

で, スタックオーバーフローとなりました.

ここは美しさを犠牲にし, ループで回避します.

LazyLinkedList.prototype.drop = function (n) {
  let l = this
  while (0 < n--)
    l = l.cdr()
  return l
}

nns.drop(10).take(10).toString()
nns.drop(100).take(10).toString()
nns.drop(1000).take(10).toString()
nns.drop(10000).take(10).toString()
nns.drop(100000).take(10).toString()
nns.drop(1000000).take(10).toString()

先頭から, 指定した関数に要素を与えた時に真として評価される値を返し続ける範囲の要素からなる遅延連結リストを返すメソッド takeWhile を実装し, 動作を確認します.

LazyLinkedList.prototype.takeWhile = function (p) {
  return p(this.car())
    ? cons(this.car(), () => this.cdr().takeWhile(p))
    : cons(null, () => null)
}

nns.takeWhile(n => n < 10).toString()
nns.takeWhile(n => n < 100).toString()

先頭から, 指定した関数に要素を与えた時に真として評価される値を返し続ける範囲の要素を捨てた, 遅延連結リストを返すメソッド dropWhile を実装し, 動作を確認します.
こちらも

LazyLinkedList.prototype.dropWhileBeauty = function (p) {
  return p(this.car())
    ? this.cdr().dropWhileBeauty(p)
    : this
}

と書けば美しいのですが, スタックオーバーフロー回避のためにループで実装します.

LazyLinkedList.prototype.dropWhile = function (p) {
  let l = this
  while (p(l.car()))
    l = l.cdr()
  return l
}

nns.dropWhile(n => n < 10).take(10).toString()
nns.dropWhile(n => n < 100).take(10).toString()
nns.dropWhile(n => n < 1000).take(10).toString()
nns.dropWhile(n => n < 10000).take(10).toString()
nns.dropWhile(n => n < 100000).take(10).toString()
nns.dropWhile(n => n < 1000000).take(10).toString()

指定した関数に要素を与えた時に真として評価される値を返す要素だけ抜き出した遅延連結リストを返す filter を実装し, 動作を確認します.

LazyLinkedList.prototype.filter = function (p) {
  return p(this.car())
    ? cons(this.car(), () => this.cdr().filter(p))
    : this.cdr().filter(p)
}

nns.filter(n => (n%2 == 0)).take(10).toString()
nns.filter(n => (n%2 == 0)).take(100).toString()

指定した関数に要素を与えた時に真として評価される値を返す要素があればその要素を, なければ null を返すメソッド some を実装し, 動作を確認します.

LazyLinkedList.prototype.some = function (p) {
  if (this.car() == null)
    return null
  else
    return p(this.car())
      ? this.car()
      : this.cdr().some(p)
}

snl.some(n => n > 8)
snl.some(n => n > 9)
swl.some(w => w.length > 8)
swl.some(w => w.length > 9)

ある要素から開始し, 指定した関数にその要素を与えた結果,
指定した関すにその結果を与えた結果,
指定した関すにその結果を与えた結果,
と無限に続けた場合の要素からなる遅延連結リストを生成する関数 iterate を実装します.

function iterate (f, a) { return cons(a, () => iterate(f, f(a))) }

すると, 先の自然数の例は

const nns2 = iterate(n => n + 1, 1)

のように定義できます.

動作確認します.

nns2.filter(n => (n%2 == 0)).take(10).toString()
nns2.filter(n => (n%2 == 0)).take(100).toString()

以上の成果を総合すると
遅延シーケンスを用いた無限素数列 in JavaScript
が実現できることになります.