【TypeScript】ジェネレーターによる遅延評価でフィボナッチ数列を生成する

はじめに

この記事は、遅延評価のことを初めて知った人が書いています。
そのため特に遅延評価周りの理解が浅いですが、ご了承ください。

やりたいこと

• 遅延評価でフィボナッチ数列を生成したい
  • 長さを指定して生成できること
  • 指定の数より小さい値のみの数列が生成できること
• JavaScriptのジェネレーターを使って遅延評価する
• フィボナッチ以外の数列を簡単に生成できるよう、設計を工夫する

環境

• Bun v1.1.34
• TypeScript Playground（ファイル分けの修正が必要）

また、この記事のコードはTypeScriptで書かれていますが、型部分を見なかったことにすればそのままJavaScriptでも動きます。

参考

• ScalaのStreamAPIおよびドキュメント

ジェネレーターを生成する

この記事では遅延評価をジェネレーターによって実装します。

ジェネレーターとは

ジェネレーターとは、データを必要なタイミングで生成するJavaScriptの仕組みです。
通常の関数は一度に全ての結果を返しますが、ジェネレーターは yield を使って、データを順番に一つずつ生成し、生成したデータをその都度返します。

ジェネレーターはジェネレーター関数によって生成できます。
例えば以下は、0以降の数字を順番にインクリメントするジェネレーター関数です。

function* generate() {
  let count = 0
  while(true) {
    yield count // countの値を返す
    count++
  }
}

これを呼び出すと、以下のような結果を得られます。

const gen = generate() // Generatorオブジェクトが入る
gen.next() // { value: 0, done: false }
gen.next() // { value: 1, done: false }
gen.next() // { value: 2, done: false }
// etc...

詳しくはMDNをご覧ください。

https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Generator

設計

今回は以下の方針でジェネレーターを生成します。

• 数列の生成方法とジェネレーターを生成する処理を分ける
• ジェネレーターを元に配列を生成するユーティリティを作る

これを実現するため、ジェネレーター周りは以下の3つに分けて実装します。

• SequenceGenerator: 数列の生成方法を決めるインターフェース
  • getElem: ジェネレーターが返す値を取得する
  • next: 次に使うSequenceGeneratorを返す
• generate 関数: ↑からジェネレーターを生成する関数
• GeneratorUtil: ジェネレーターを配列に変換するユーティリティ
  • take: 指定された数の値を取り出す
  • takeWhile: 指定された条件を満たすうちは値を取り出す

実装

この項の実装は全てgenerator.tsに書きます。

SequenceGenerator

• 型パラメーターTを設けることで、次のジェネレーターが返す値を決める
• この型パラメーターはインターフェースの実装時に手動で決める

generator.ts

interface SequenceGenerator<T> {
  getElem(): T
  next(): SequenceGenerator<T>
}

フィボナッチ数列の項では、このインターフェースを実装（implements）して数列の生成方法を定義します。

generate 関数

• SequenceGeneratorのインスタンスを受け取る
• ↑ではカバーできない、遅延評価しない初期値も一緒に受け取る
• 実行順：
  1. 与えられた初期値（init）をyieldする
  2. getElem() と next() を使って数列の次の値を順次yieldする

generator.ts

function* generate<T>(seq: SequenceGenerator<T>, init: T[] = []) {
  for (const elem of init) { yield elem } // 初期値の処理
  while(true) {
    yield seq.getElem() // 値を返す
    seq = seq.next() // seqを更新する
  }
}

GeneratorUtil

• 全てのメソッドは上記2つに依存せず、素のGeneratorオブジェクトを使う
• ジェネレーターは複製できなそうなので、メソッドは全て破壊的
• 有限な長さのジェネレーターには対応しない

generator.ts

const GeneratorUtil = {
  // 指定された数の要素を取り出す
  take<T>(g: Generator<T>, count: number): T[] {
    const result: T[] = []
    for (let i = 0; i < count; i++) {
      result.push(g.next().value)
    }
    return result
  },
  // 指定された条件を満たすうちは要素を取り出す
  takeWhile<T>(g: Generator<T>, func: (elem: T) => boolean): T[] {
    const result: T[] = []
    while(true) {
      const elem = g.next().value
      if(!func(elem)) return result
      result.push(elem)
    }
  }
} as const

フィボナッチ数列の生成方法を定義する

フィボナッチ数列は前の2つの値を足した結果を並べた数列です。
例えば最初の2つが1, 3だとしたら、[1, 3, 4, 7, 11, 18, ...] となります。

FibNumber

FibNumberはSequenceGeneratorインターフェースを実装し、数列を生成する方法を定義するクラスです。

コンストラクタで前の2つの値a, bを受け取り、それに基づいてメソッドを以下のように実装しています。

• getElem(): フィボナッチ数列の今の値（前の2つの値の合計）を返す
• next(): 前の2つの値を更新した新しいインスタンスを返す

fibonacci.ts

class FibNumber implements SequenceGenerator<number> {
  constructor(
    private readonly a: number,
    private readonly b: number,
  ) {}
  getElem() { return this.a + this.b }
  next() { return new FibNumber(this.b, this.b + this.a) }
}

このクラスのインスタンスはgenerate関数から使用されます。

初期値の扱いをラップする

このままフィボナッチ数列を生成してもいいのですが、少し気になる点があります。
現在の実装の性質上、フィボナッチ数列の最初の2つの値は以下の2箇所で使われます。

• FibNumberのインスタンス化
• generate関数のinit引数

クライアントで同じ数字を2つ書くのは面倒なので、以下のようにラップします。

fibonacci.ts

function fib(a: number, b: number) {
  const head = new FibNumber(a, b)
  return generate(head, [a, b])
}

フィボナッチ数列を生成する

準備はできたので、さっそくフィボナッチ数列を生成します。
手順はこのようになります。

1. fib関数を最初の2つの値とともに呼び出し、ジェネレーターを取得
2. 1のジェネレーターをGeneratorUtilのメソッドに入れる
3. フィボナッチ数列が取得できる

例えばこのようになります。

import { fib } from "./fibonacci"
import { GeneratorUtil } from "./generator"

// [2, 4]から始まる長さが10のフィボナッチ数列
GeneratorUtil.take(fib(2, 4), 10)
// [2, 4, 6, 10, 16, 26, 42, 68, 110, 178]

// [1, 3]から始まる1000未満のフィボナッチ数列
GeneratorUtil.takeWhile(fib(1, 3), e => e < 1000)
// [1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843] 

全体像

client.ts

// フィボナッチ数列を生成する

import { fib } from "./fibonacci"
import { GeneratorUtil } from "./generator"

// [2, 4]から始まる長さが10のフィボナッチ数列
GeneratorUtil.take(fib(2, 4), 10)

// [1, 3]から始まる1000未満のフィボナッチ数列
GeneratorUtil.takeWhile(fib(1, 3), e => e < 1000)

fibonacci.ts

// フィボナッチ数列の生成の仕方を定義する
// また、generate関数をラップして、初期値の設定を隠蔽する

import { SequenceGenerator, generate } from "./generator"

class FibNumber implements SequenceGenerator<number> {
  constructor(
    private readonly a: number,
    private readonly b: number,
  ) {}
  getElem() { return this.a + this.b }
  next() { return new FibNumber(this.b, this.b + this.a) }
}

export function fib(a: number, b: number) {
  const head = new FibNumber(a, b)
  return generate(head, [a, b])
}

generator.ts

// 数列の生成方法を知るオブジェクトから数列を生成するジェネレーターを定義する
// 数列は遅延評価され、必要なとき（e.g. GeneratorUtilから参照されたとき）に計算される

export interface SequenceGenerator<T> {
  getElem(): T
  next(): SequenceGenerator<T>
}

export function* generate<T>(seq: SequenceGenerator<T>, init: T[] = []) {
  for (const elem of init) { yield elem } // 初期値の処理
  while(true) {
    yield seq.getElem() // 値を返す
    seq = seq.next() // seqを更新する
  }
}

export const GeneratorUtil = {
  // 指定された数の要素を取り出す
  take<T>(g: Generator<T>, count: number): T[] {
    const result: T[] = []
    for (let i = 0; i < count; i++) {
      result.push(g.next().value)
    }
    return result
  },
  // 指定された条件を満たすうちは要素を取り出す
  takeWhile<T>(g: Generator<T>, func: (elem: T) => boolean): T[] {
    const result: T[] = []
    while(true) {
      const elem = g.next().value
      if(!func(elem)) return result
      result.push(elem)
    }
  }
} as const

おまけ: トリボナッチ数列

generator.tsのAPIはフィボナッチ数列以外にも対応しているので、例えばトリボナッチ数列（前の3つの数を足す）を簡単に実装できます。

import { SequenceGenerator, generate } from "./generator"

class TribNumber implements SequenceGenerator<number> {
  constructor(
    private readonly a: number,
    private readonly b: number,
    private readonly c: number,
  ) {}
  getElem() { return this.a + this.b + this.c }
  next() {
    return new TribNumber(this.b, this.c, this.c + this.b + this.a)
  }
}

GeneratorUtil.take(generate(new TribNumber(1, 2, 3), [1, 2, 3]), 10)
// [1, 2, 3, 6, 11, 20, 37, 68, 125, 230]