遅延シーケンスを用いた無限素数列 in JavaScript
で使っている遅延連結リストを function を使わずに実装
するために必要な前提知識の再確認および演習です.

function と =>

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

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

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

本記事では, 上記機能を使わず「=>」を使っていきます.
(function を使う版はこちら)

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

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

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

関数リテラル

階乗を例にします.

n => (n == 0)?1:n*_(n - 1)
のような関数の _ の箇所でこの関数自身を呼び出したい場合,
(f => f(f))(g => n => (n == 0)?1:n*g(g)(n - 1))
のように書くことができます.

「引数として関数を与えると, その関数を引数としてその関数を呼び出す関数 (f => f(f))」に, 『引数を与えると「本来やりたかった関数」を返す関数』を与えると得られる関数は, 基本的には「本来やりたかった関数」そのものですが, これを内包する関数 (g => ...) の部分は『引数を与えると「本来やりたかった関数」を返す関数』を仮引数 g で受け取っていることになりますので, g に g を引数として与えると「本来やりたかった関数」になります.
つまり「本来やりたかった関数」の中で g(g) は「本来やりたかった関数」自身を表すことができます.

上記定義中の変数 f と g はどちらもどちらのスコープにも含まれないので
同じ変数名を使っても構いません.
(もちろんスコープ内の他の変数名と被ってはいけません.)

(f => f(f))(g => n => (n == 0)?1:n*g(g)(n - 1)
(f => f(f))(f => n => (n == 0)?1:n*f(f)(n - 1)
(g => g(g))(g => n => (n == 0)?1:n*g(g)(n - 1)
(x => x(x))(x => n => (n == 0)?1:n*x(x)(n - 1)

などは全て同じものです.

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

(g => g(g))(g => n => (n == 0)?1:n*g(g)(n - 1))(5)

関数リテラルを変数に束縛

関数リテラルを変数に束縛することで, 関数に名前をつけてもよいです.

const factorial = (g => g(g))(g => n => (n == 0)?1:n*g(g)(n - 1))

動作確認

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

連結リスト (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 って何? という方は
こちら
)

動作確認

数値列の要素の総和

(g => g(g))(g => l => (l == null)?0:(car(l) + g(g)(cdr(l))))(snl)

数値列の要素の総積

(g => g(g))(g => l => (l == null)?1:(car(l) * g(g)(cdr(l))))(snl)

数値列の要素の最大値

(g => g(g))(g =>
  (l, a) =>
    (a == null)?g(g)(cdr(l), car(l)):(
      (l == null)?a:(
        (a < car(l))?g(g)(cdr(l), car(l)):g(g)(cdr(l), a))))(snl)

単語列の要素の最長単語

(g => g(g))(g =>
  (l, a) =>
    (a == null)?g(g)(cdr(l), car(l)):(
      (l == null)?a:(
        (a.length < car(l).length)?g(g)(cdr(l), car(l)):g(g)(cdr(l), a))))(swl)

reduce の実装

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

const reduce = (g => g(g))(g =>
  (l, f, a) => 
    (a == null)?g(g)(cdr(l), f, car(l)):(
      (l == null)?a:g(g)(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(swl, (a, x) => (a.length < x.length)?x:a)

配列を連結リストに変換する関数を 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 に変換) する処理を記述
し, 動作確認してください.

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

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

連結リストの定義を変更

連結リスト型をオブジェクト型で定義し,
オブジェクトのプロパティをインスタンスメソッドとして
car, cdr, reduce を使えるようにします.

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

const cons = (a, b) => { return {
  car: () => a,
  cdr: () => 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)))))))))

Object のプロパティを使って, 連結リスト.reduce(関数, 初期値) のように
reduce を呼べるようにします.

(メソッドを追加するので, 定義をクリアし, cons の定義を改め,
サンプル snl, swl も定義し直します.)

const cons = (a, b) => {
  let o = {
    car: () => a,
    cdr: () => b
  }
  o.reduce = (f, a) =>
            (a == null)?o.cdr().reduce(f, o.car()):(
              (o.car() == null)?a:o.cdr().reduce(f, f(a, o.car())))
  return o
}
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)))))))))

動作確認

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)

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

定義および基本動作の確認

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

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

const cons = (a, b) => {
  let o = {
    car: () => a,
    cdr: b
  }
  o.reduce = (f, a) =>
    (a == null)?o.cdr().reduce(f, o.car()):(
      (o.car() == null)?a:o.cdr().reduce(f, f(a, o.car())))
  o.toString = () =>
    (o.car() == null)?"":(o.car() + ", " + o.cdr().toString())
  return o
}

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)))))))))

動作確認

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)
snl.toString()
swl.toString()

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

メソッド追加

先に動作確認のためのメソッドを追加するため, cons の定義を変更します.
各メソッドは後ほど解説します.

const cons = (a, b) => {
  let o = {
    car: () => a,
    cdr: b
  }
  o.reduce = (f, a) =>
    (a == null)?o.cdr().reduce(f, o.car()):(
      (o.car() == null)?a:o.cdr().reduce(f, f(a, o.car())))
  o.toString = () =>
    (o.car() == null)?"":(o.car() + ", " + o.cdr().toString())
  o.take = n => (n == 0)
    ? cons(null, () => null)
    : cons(o.car(), () => o.cdr().take(n - 1))
  o.drop = n => {
    let l = o
    while (0 < n--)
      l = l.cdr()
    return l
  }
  o.takeWhile = p => p(o.car())
    ? cons(o.car(), () => o.cdr().takeWhile(p))
    : cons(null, () => null)
  o.dropWhile = p => {
    let l = o
    while (p(l.car()))
      l = l.cdr()
    return l
  }
  o.filter = p => p(o.car())
    ? cons(o.car(), () => o.cdr().filter(p))
    : o.cdr().filter(p)
  o.some = p => {
    let l = o
    while (l.car() != null && !p(l.car()))
      l = l.cdr()
    return l.car()
  }
  return o
}

自然数列

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

const iterate = (g => g(g))(g => (f, a) => cons(a, () => g(g)(f, f(a))))

無限シーケンスの例として自然数列を iterate を使って定義します.

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

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

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

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

メソッド解説＆動作確認

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

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

定義の該当部分は

  o.take = n => (n == 0)
    ? cons(null, () => null)
    : cons(o.car(), () => o.cdr().take(n - 1))

です.

drop は先頭から指定した個数を要素を取り除いた遅延連結リストを返します.
自然数列で動作確認をします.

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()

定義の該当部分は

  o.drop = n => {
    let l = o
    while (0 < n--)
      l = l.cdr()
    return l
  }

です.

  o.drop = n => (n == 0)?o:o.cdr().drop(n - 1)

のように実装すると再帰構造で記述できて美しいのですが,
n が大きい場合にスタックオーバーフローを起こしますので,
ループにしておきます.

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

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

定義の該当部分は

  o.takeWhile = p => p(o.car())
    ? cons(o.car(), () => o.cdr().takeWhile(p))
    : cons(null, () => null)

です.

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

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()

定義の該当部分は

  o.dropWhile = p => {
    let l = o
    while (p(l.car()))
      l = l.cdr()
    return l
  }

です.

こちらも再帰で

  o.dropWhile = p => p(o.car())?o.cdr().dropWhile(p):o

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

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

動作を確認します.

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

該当定義は

  o.filter = p => p(o.car())
    ? cons(o.car(), () => o.cdr().filter(p))
    : o.cdr().filter(p)

です.

some は, 指定した関数に要素を与えた時に真として評価される値を返す要素があればその要素を, なければ 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)))))))))

で試験します.

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

定義の該当部分は

  o.some = p => {
    let l = o
    while (l.car() != null && !p(l.car()))
      l = l.cdr()
    return l.car()
  }

です.

こちらも再帰で

  o.some = p => (o.car() == null)
    ? null
    : ( p(o.car())
          ? o.car()
          : o.cdr().some(p))

と書けば美しいですが, ループで.

素数列の定義

以上の成果を総合すると
遅延シーケンスを用いた無限素数列 in JavaScript
の function を使わない版ができます.

そうすると (上記 cons と iterate の定義の上で) 素数列は次のように書けます.

const primeNumbers = (g => g(g))(g => x =>
  cons(x,
    () => g(g)(
      iterate(n => n + 1, x + 1)
        .dropWhile(
           n => g(g)(2)
                  .takeWhile(c => c*c <= n)
                  .some(d => n%d == 0))
        .car())))(2)

素数列は『見つかっているうちの最後の素数 x を与えると「自分自身 g(g) に, x の次の素数を与えて得られる遅延シーケンス g(g)(...)」の先頭に x を付加する cons(x, () => ...) ような関数 f』に 2 を与えたものです.

ただし x の次の素数は, x より 1 大きい数から, 1ずつ大きくなる数列 iterate(...) の要素を, 『自然数 n を与えると, 素数列 g(g)(2) の先頭から, 二乗が n 以下である間, 要素を取り出した列 .takeWhile(...) の中に n を割り切るものがあれば真を返すような関数 .some(...)』に与えて, 真を返す間の要素を捨てたもの dropwhile(...) の最初の要素 .car(...) です.

素数列を求めるのに素数列を使っていますが, 次の素数の候補に対して, 二乗がその数以下であるような素数までは求まっているので, 大丈夫.
遅延シーケンス万歳！

動作確認

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

2から昇順100個の素数を列挙

primeNumbers.take(100).toString()

100未満の素数を列挙

primeNumbers.takeWhile(n => n < 100).toString()

9000以上, 10000未満の素数を列挙

primeNumbers.dropWhile(n => n < 9000).takeWhile(n => n < 10000).toString()

10未満の素数の総和

primeNumbers.takeWhile(n => n < 10).reduce((a, x) => a + x)

10001番目の素数

primeNumbers.drop(10000).car()

200万未満の素数の総和

primeNumbers.takeWhile(n => n < 2000000).reduce((a, x) => a + x)

と思ったけど, 最後の例は stack オーバーフローになってしまいました.