Zenn
👻

遅延コレクションライブラリ「leseq」を公開しました

2022/03/17に公開
10件
TypeScript
npm
tech

＊2022/3/18 適当だった表現をいくつか修正＊
＊2022/3/20 ご指摘を受けて1-1を全面的に書き直し＊
＊2022/12/22 遅延評価コレクションという言葉を遅延コレクションに修正＊

Tree Shaking親和性が高く、機能の追加が容易な遅延コレクション（いわゆるLazy List/Collection）ライブラリを公開しました。
https://github.com/ugaya40/leseq

1.遅延コレクションとは？

まず遅延コレクションに馴染みがない方のために遅延コレクションについて僕が考える簡単な特徴となぜ必要とされるのかについて説明します。ご存じの方はこの項目は飛ばしてください。

1-1.最小限の読み込み

こんなコードを考えてみましょう。

例1
const source = [1, 2, 1, 4, 3, 6, 7, 4, 9, 10];
const result = source
  .filter((i) => i < 7)
  .map((i) => i * i)
  .slice(0, 3); //先頭から3つ

これは大変富豪的なコードです。このコードの結果は[1,4,1]です。まずfilterはsource全部を読み取り[1, 2, 1, 4, 3, 6, 4]を返し、mapは[1, 4, 1, 16, 9, 36, 16]を返し、しかしその結果の最初の3つしか必要ではありませんでした。

for文で書けば大分効率的になります。

例2
const source = [1, 2, 1, 4, 3, 6, 7, 4, 9, 10];
const result: number[] = [];
for (const i of source) {
  if (i < 7) {
    result.push(i * i);
    if (result.length == 3) break;
  }
}

sourceは最小限の[1, 2, 1]までしか読み取られていませんし、filterやmapが返す中間配列もありません。

遅延コレクションライブラリを使うとこういうコードになります。leseqでの例です。

例3
const source = [1, 2, 1, 4, 3, 6, 7, 4, 9, 10];
const result = from(source).pipe(
  filter((i) => i < 7),
  map((i) => i * i),
  take(3) //最初の3つだけ取得する
).toArray();

このコードは一見例1に似ていますが、例2の場合と同じくsourceは最小限の[1, 2, 1]までしか読み取られませんし、余計な中間配列も生み出されません。
こういった「最小限の所までしか列挙しない/読まない」のが遅延コレクションの特徴の一つです。この性質から、実は無限シーケンスを扱うことも可能です。なぜこういった事が可能なのかについては詳細は省きますが、これはIterator/Generatorの魔力です。Iterator/Generatorについては以下の記事が素晴らしく詳しいです。
https://zenn.dev/qnighy/articles/112af47edfda96

また、例が複雑になってくるとfor文だと状態変数が増えてわかりづらくなってきます。
まずは先にleseqでの例を示します。

例4-1
const source = [1,4,10,1,4,11,12,3,11,8,1,4,5,2];
const result = from(source).pipe(
  uniq(), //重複を排除
  filter((i) => i < 11), 
  scan(0,(sum, i) => sum + i), //現在までの合計値に現在の値を加えて返す
  take(5) //最初の5つだけ取得する
).toArray();
//result: [1, 5, 15, 18, 26]

uniqは重複を排除します。scanはreduceの途中経過が列挙される版です。scanで現在までの合計値に現在の値を加えて返します。1の次に4が流れてきて5、その次に10が流れてきて15という形になっているわけです。

これをfor文で書くとこうなります。

例4-2
const source = [1,4,10,1,4,11,12,3,11,8,1,4,5,2];
const result:number[] = [];
const appeared: number[] = [];
let currentResult: number = 0;
for(const i of source) {
  if(i < 11 && appeared.indexOf(i) == -1) {
    currentResult += i;
    appeared.push(i);
    result.push(currentResult);
    if(result.length == 5) break; 
  } 
}
//result: [1, 5, 15, 18, 26]

大分読みにくくなってきたのでないでしょうか？。appearedという状態変数を用意して重複を排除し、現在の合計値はcurrentResultに保存しています。

例4-2(for文の例)では結果が確定する8までしかsourceを読み込みませんが、例4-1(leseqでの例)での例でも同じです。8までしか読み込みません。

遅延コレクションライブラリを使用すると同じ読み取り量にも関わらずfor文で増えがちな状態変数が隠蔽され、意図が明快になります。

1-2.結果を求められるまで列挙しない

先程のleseqの例、実はどれもtoArrayを呼び出すまでは列挙を行いません。「必要になるまで列挙を行わない」のも遅延コレクションの特徴です。

例5
//この行では列挙しない、元配列は何も読まれていない
const source =from([10,1,1,3,6,8,9,5,4,2,1,1]).pipe(
  filter(i => i < 5),
  uniq(),
  take(3)
);

//列挙1:
//結果の一つだけ読む。列挙が行われる。
//しかし一つだけ結果を読んでforから抜けているため、
//元配列は[10,1]の部分までしか列挙されていない。
for(const one of source) {
  console.log(one); //console: 1
  break;
}

//列挙2:
//findは条件を満たす値最初の値を返す。
//この場合元配列は[10,1,1,3]までしか列挙されていない
const result = source.value(find(i => i * i > 8));
//result: 3

//列挙3:
//この場合配列に変換するためsource全て(元配列全てではない)を列挙する。
//元配列は[10,1,1,3,6,8,9,5,4]まで読まれる。
const array = source.toArray();
//array:[1,3,4]

元配列が列挙されたのは列挙1で[10,1]まで、列挙2で[10,1,1,3]まで、列挙3で[10,1,1,3,6,8,9,5,4]までです。列挙2のvalue()は結果を求める関数で、引数として結果を求める関数を一つ取ります。つまり基本的にvalue呼び出しでは、引数で与えられたvalue用関数に基づき最小限の列挙が行われます。find()は引数で与えられた条件を満たす最初の値まで列挙し、その値を返す関数です。

実際に上の例を実行しているコードはこちらです。この例ではappearedIteratorという列挙した値を記録するIteratorを定義して、実際に余計なものが列挙されなかったことを確認しています。

1-3.不変である

入力ソースを変更しないし、影響を与えません。これまでの例でも入力ソースは一切変更されていません。

1-4.遅延コレクションのメリット・デメリット

とにかく最小限の列挙が遅延コレクションの代表的な特徴と言っていいでしょう。
そして複雑な処理を描いた場合にfor文と比べてループ用の状態変数が隠蔽されているため、意図が分かりやすくなるもの特徴です。

ただ小さな配列に対する処理では、遅延可能にするための内部的なオブジェクト生成コストなどで、Array標準のmapやfilterなどで配列を何度か全部舐めした方が処理効率が良い場合もあります。 しかし、配列を全部舐めするような処理は、何度か重ねると読み取り量が指数関数的に増大していきます。入力配列のサイズが予測できないライブラリの開発などでは致命的になる事もあります。

遅延コレクションライブラリは基本的はfor文で最小の読み取り量のコードを書いた場合に加えてわずかなオブジェクト生成コストが乗るだけですので僕なんかは常に遅延コレクションライブラリ(僕の場合はleseq)を使用したコードを書くようにしています。入力配列のサイズの増加に対して予測可能な最小限の読み取り量の変化で済ませられるのは遅延コレクションの大きなメリットです。

2.leseqの特徴

2-1.遅延コレクションライブラリ

leseqは上で説明した通りの特徴を全て備えた遅延コレクションライブラリです。
reverse(),groupBy(),orderBy()などのそもそも原理的に全て列挙してからでないと正しい値を返せないコレクション操作関数を除き、全ての関数が必要なところまでしか入力ソースを列挙しません。
ただ値のキャッシュはしていません。副作用前提のコードを容認するためです。

2-2.TreeShaking親和性

rxjsライクな構文を採用し、一切の副作用のあるファイルを排除する(もちろん"sideEffect":falseです)事でTreeShaking親和性を高めています。
TreeShaking親和性はleseq作成の大きな動機の一つであり、内部実装もこだわっています。

TreeShakingについてはこの記事が素晴らしく詳しいです。
https://www.kabuku.co.jp/developers/tree-shaking-in-2018

書き心地は本来メソッドチェインの方が当然良いのですが、メソッドチェインが可能という事はシーケンスのprototypeから全ての関数が呼び出し可能、つまりは定義したコレクション操作用関数がシーケンスを作成した時点で全てロードされてしまうという事です。

leseqはpipe()やvalue()といった一見冗長な構文を介することで使用するコレクション操作用関数のみをバンドルする事ができます。

たとえば以下のようなコードをrollupでバンドルした際のバンドルアナライズの結果は以下の通りです。

import {from, map, take} from 'leseq';

export const result1 = from([1,2,3,4,5]).pipe(
  map(i => i * i),
  take(3)
).toArray();

//result1: [1,4,9]

1.21KB gzipped
1.21KB gzipped
seq.jsはCoreオブジェクトです。他は使用しているコレクション操作関数のみがbundleされている事がわかります。

2-3.Async Iteratorサポート

leseqではasync iteratorをサポートし、各コレクション操作関数に渡す関数がPromiseを返す事ができるようになっています。

const sleep = (milliseconds: number) => new Promise(resolve => setTimeout(resolve,milliseconds));

//from iterable to async iterable.
const result = await from([1,2,3,4]).value(toAsync()).pipe(
  mapAsync(async i => {
    await sleep(1000);
    return i * i;
  }),
);

for await (const one of result) {
  console.log(one);
}
//1 seconds later... result: 1
//2 seconds later... result: 4
//3 seconds later... result: 9
//4 seconds later... result: 16

上記例では、.value(toAsync())を用いてiterableをasync iterableに変換していますが、最初からasync iterableのシーケンスを生成することも可能です。
また、上記例のようにiterableからasync iterableへの変換はいつでも可能ですが、async iterableはiterableに変換することも戻すこともできません。これはasync iterableとPromiseの原理上の制限です。

元々はSubtleCrypto.digest()がPromiseしか返さなかったため作成しましたが、コレクション操作の結果に基づいたfetchやNodeでのファイル操作などでも有用でしょう。

2-4.簡単に追加可能なコレクション操作関数

これはleseqを作成した大きな理由の一つで、詳細な方法はドキュメントに譲りますが、比較的簡単に独自のコレクション操作関数を増やす事ができます。
たとえばmap相当の関数を自作する場合はこれだけです。

const mapOriginal = <T, TResult>(func: (arg: T) => TResult): Operator<T, TResult> =>
  function* mapOriginal(source: Seq<T>): Gen<TResult> {
    for (const i of source) {
      const result = func(i);
      yield result;
    }
  };

const result1 = from([1,2,3,4,5]).pipe(mapOriginal(i => i * i)).toArray();
//result1: [1,4,9,16,25]

async versionでもこれです。

const mapAsyncOriginal = <T, TResult>(func: (arg: T) => Promise<TResult>): AsyncOperator<T, TResult> =>
  async function* mapAsyncOriginal (source: AsyncSeq<T>): AsyncGen<TResult> {
    for await (const i of source) {
      const result = await func(i);
      yield result;
    }
  };
  
const sleep = (milliseconds: number) => new Promise(resolve => setTimeout(resolve,milliseconds));

const result = await fromAsAsync([1,2,3,4,5]).pipe(
  mapAsyncOriginal(async i => {
    await sleep(1000);
    return i * i;
  }),
).toArrayAsync();

//5 seconds later... result2: [1,4,9,16,25]

*がついたfunction宣言はGenerator関数です。Generator関数に同じ名前がついているのはスタックトレースのためです。基本的にスタックトレースにはGenerator関数の名前が載りますので、名前はきちんとつけた方が良いでしょう。

2-5.シンプルな同値比較戦略

入力シーケンスがnumber,string,booleanなどのプリミティブ値ではなくオブジェクトの場合、重複を弾くuniq、グループ化するgroupByなどではオブジェクトの同値性比較を行わなければなりません。
他の遅延コレクションライブラリなどでは、デフォルトでオブジェクトのハッシュ値などを計算して採用するケースも散見しますが多くの場合ハッシュ値の算出はオーバーキルです。
leseqではシンプルに同値性を保証するプリミティブな値を返す関数を渡すことを一貫して推奨してします。詳細はドキュメントに譲ります。

2-6.100%TypeScript/No Dependency

これはそのままですね。ただNo Dependencyについては今後変更するかもしれません。

3.他のライブラリとの違い/あるいは何故選ばなかったか

各ライブラリを選ばなかった理由は、基本的にleseqの作成動機の裏返しであり、つまりは僕個人の動機に強く根ざしています。また、本義が遅延コレクションライブラリではないライブラリも混ざっていますが、あくまでも遅延コレクションライブラリとしての評価です。

lodash

lodashで採用されている遅延と言われるものは、実は通常の全部舐め関数呼び出しを記憶しておいて、実行を遅延させる事ができるもので、ここで説明してる遅延コレクションとはだいぶ違ったものです。
解説記事がありました。
http://filimanjaro.com/blog/2014/introducing-lazy-evaluation/
また、無限シーケンスに対応できません。長さが決まっていて、インデクサアクセス可能な、配列ライクなものしか受け付けません。

そしてどうも遅延周りを完全に制御できているわけではないのか実際わけのわからない挙動をします。複雑すぎるんだと思います。。軽く検証しただけでこれです。

あとlodash周りは情報の錯綜すごい。

immutable.js

immutable.jsはちゃんとこの記事の意味での遅延です。
ただメソッドチェインであるため、便利になればなるほどTreeShaking親和性に疑問が残ります。そもそも現在はTreeShaking周り怪しいっぽいです。

https://github.com/immutable-js/immutable-js/issues/1190

そして。。。。旧Facebook社お得意の無言廃棄かもしれません。(draft.jsでも泣いた)
https://www.reddit.com/r/reactjs/comments/83gny7/has_facebook_abandoned_immutable_js/
https://github.com/immutable-js/immutable-js/issues/1689

IxJS

IxJSはかなり遅れて発見した(つまりleseqを作ってから発見した)のですが、ちゃんとこの記事の意味での遅延コレクションです。そもそもがRxJSと同じReactiveX内のリポジトリですし、きちんとasync iteratorサポートもあります。TreeShaking親和性も高く、正直かなり良いです。

ただちょっとオリジナル関数作成が面倒なんです。たとえばmapの実装はこちらです。
https://github.com/ReactiveX/IxJS/blob/master/src/iterable/operators/map.ts
各オペレータごとに専用のIterableクラスを作成しています。
IxJSというのは元々C#の標準ライブラリにある遅延コレクション機能LINQの拡張として実装されたInteractive ExtensionsのJS版です。(あ、Rxもそうです。元々はC#用のReactive Exntesionsで、2010年にはすでにあります。)
思いっきりIxJSもLINQスタイルの実装も受け継いでいるんですね。leseqでのmapの実装のこれと較べると大分面倒な気がしています。
https://github.com/ugaya40/leseq/blob/main/packages/leseq/src/operators/map.ts

ただこのIxの実装はこの実装でメリットがあると思っています(後述する通りそのメリットは享受していませんが)。
pipe形式やメソッドチェイン形式では、各オペレータが新しいIterableを次のオペレータに渡します。leseqでは無名のIterableを渡していますが、IxJSのように各オペレータが専用のクラスのIterableを返すという事は、それを渡された次段のオペレータの方では「前段のオペレータが何だったか分かる」という事です。これは最適化の可能性を拡げます。たとえばこんな実装を見てみます。

from([1,2,3,4,5]).pipe(
  filter(i => i % 2 == 0),
  filter(i => i > 3)
)

このシーケンス、filterを2回呼ぶのはまったくの無駄です。ところがIxではfilterはFilterIterableを返します。二つ目のfilterでは前段のオペレータがfilterである事がわかったので、前段のfilterの条件とマージして実際に実行するコードはこんな感じにすることも可能なわけです。

from([1,2,3,4,5]).pipe(
  filter(i => i % 2 == 0 && i > 3),
)

他にもソート済みのシーケンスである事がわかれば特定のオペレータでの操作をスキップできたりするかもしれません。
が、実際はIxJSではそういった最適化は一切されていません。
となると実装が面倒なだけではないのかな。。。他にメリットあるのかな？。。
あと同値比較戦略がださい気がします。一個一個Compareするのはどうなんでしょう。
https://github.com/ReactiveX/IxJS/blob/master/src/iterable/operators/distinct.ts

4.leseqの今後

実は1年半？ぐらい前、leseqのベースがあり、今もちまちま付け足して使っています。現在のプロダクションコードでも使用していますし、当分はこれを使っていきますし、メンテしていく予定です。

明らかに少ないコレクション操作関数の追加はもちろん継続的にやっていきます。

あとやっておきたいのはorderByAsyncの書き直し、あるいは同等機能のオペレータの追加ですね。基本的に全ての非同期版オペレータは関数を渡せる場合、その関数がPromiseを返せるようにしてあります。しかしorderByだけは、内部でArray.Sortを使用しているためorderByAsyncでも渡せる関数は同期版のみになっているのです。Array.Sortを使わないでパフォーマンスを確保するとなると、いけてるTimSortライブラリ(これとか？)を使う必要があるかもしれません。その場合はNo dependenciesは返上です。(TimSortみたいな複合的なアルゴリズムを自分で実装するっていうのはかなりしんどそうなので)

おわりに

僕は元々はC#ばっかりやっていて、WebフロントはDHTMLの時代からワープしてきました。

JQueryの時代すら経験がありません。npm？何それ？から初めて現在のWebフロントの覚える事の膨大さに呆然としつつも、約1年半前からがっつり楽しんでやっています。

Webフロントをはじめてはじめてのアウトプットです。知識不足は自覚していますし、それ故の間違いや、非効率な部分があるかもしれませんのでご指摘がある方は是非お願いいたします。

Discussion

ZuishinZuishin

はい、答えは2回です。filterで全部読まれ、またmapで全部読まれることになります。2度配列を全部舐め、2度全列挙しています。ループを2回まわすのと一緒です。しかし本来この処理はループ一回で済むはずです。

本当ですか？
JavaScript の filter は配列を返すんじゃありませんでしたっけ？
filter で返された配列の要素数が一つなら、map が読むのは一つじゃありませんか？

ugaya40ugaya40

ごめんなさい、これ表現間違ってますね。直します。

ugaya40ugaya40

例も変えて、言いたい事が伝わるよう修正しました。間違えた事を伝える形になっていましたね。。ご指摘ありがとうございます！

ZuishinZuishin

2度同じサイズの配列を全部舐めています。

このようなフィルタリングで全部通す条件なら、遅延評価でやっても同じ要素を二回舐めますよね。
1 から 10 まで数え、もう一度 1 から 10 まで数えても、1、1、2、2、のように 1 から 10 までを 2 回ずつ数えても、順番が違うだけでやることは同じです。

配列作成のオーバーヘッドはもちろんあるでしょうが、計算量が減ることはないと思います。処理系の実装とユーザーコード次第で、列挙のオーバーヘッドが配列作成を上回ることもあるかもしれません。(配列を引数に配列を返す場合、Enumerator の作成が不要になります)

遅延評価の本領は、配列のようなサイズも中身も決まっているデータでは発揮できなくて、一つ一つの要素を実行時に計算する場合にこそ有効だと思います。

たとえば、JavaScript の場合、filter を作るためにはまず配列を作成しなければいけません。
ところが、その元となるデータが無限に送られてくる場合(あるいは極端に大きい場合)、配列を作成する段階でフリーズします。
遅延評価であれば、データが終了条件を満たした時点でいつでも列挙をやめられるので、無限のデータに対応できますし、列挙時にイベントを発行してプログレス表示に利用することも容易になります。

そのあたりのメリットが述べられているのなら理解できますが、「二回舐める」ことについては、何を問題にされているのか、理解が及びませんでした。

ugaya40ugaya40

このようなフィルタリングで全部通す条件なら、遅延評価でやっても同じ要素を二回舐めますよね。

おっしゃる通りで「二回舐める」という表現に僕がこだわっていたため、場当たり的に例を変えたらよりメリットがあらわせていませんでした。「二回舐める」という表現はやめてどういう風に表現するか例を含めてちょっと考えてみますね。

ugaya40ugaya40

  1. 最小の読み取り
    https://stackblitz.com/edit/typescript-mtnv5b?file=index.ts
    のよう例を作り、まずmapやfilterを富豪的に使うと余計な読み取りが起きる事・for文だときちんと書ける事・遅延評価コレクションでもforと同じ読み取り回数でできる事を示す。

  2. for文だと増える状態変数の隠蔽
    重複排除の例を追加して状態変数が隠蔽されていてfor文よりわかりやすい事を示す。

の流れで後で修正する予定です！(多分今日は無理そう)。

遅延評価のメリットと違うではないかというお話もありそうですが、遅延評価コレクションライブラリのメリットとしてなので十分かなと。
ご指摘ありがとうございます。7年ぶりに技術記事書いたら適当過ぎました。

amay077amay077

こんにちは、leseq 使わせてもらってます。

Rx の bufferWithCount に相当する operator を自作しようと、chunk.ts を参考に、 chunkWithCount を書いてみました。

const chunkWithSkip = <T>(size: number, skipCount: number): Operator<T, readonly T[]> =>
  function* chunk(source: Seq<T>): Gen<readonly T[]> {
    let ch: T[] = [];
    const s = source.toArray();
    for (let i = 0; i < s.length; i++) {
      const one = s[i];
      ch.push(one);
      if (ch.length === size) {
        yield ch;
        i = i - (size - skipCount);
        ch = [];
      }
    }    if (ch.length != 0) {
      yield ch;
    }
  };

console.log(from([1,2,3,4,5]).pipe(chunkWithSkip(3, 1)).toArray());

> [1, 2, 3]
> [2, 3, 4]
> [3, 4, 5]
> [4, 5]

期待する結果は得られていますが、 source.toArray() や for (i = 0; xxx しているのがイマイチだなあと感じています。
こう書いた方がスマート（パフォーマンスも良い）というのがあったらアドバイス頂けると嬉しいです。

ugaya40ugaya40

使っていただいてありがとうございます！
完全に誰にも使われていないと思って孤独にメンテしてました！w

気付くの遅れてすいません・・zenn用に連携しているgoogleアカウントが普段使っているメアドと別のものでして・・。そして今見たらzennは別のメールアドレスに通知を飛ばす事はできないようでして。。今後については考えます。

何はともあれやってみました！

const chunkWithSkipNew = <T>(
  size: number,
  skipCount: number
): Operator<T, readonly T[]> =>
  function* chunkWithSkipNew(source: Seq<T>): Gen<readonly T[]> {
    //インデックス用
    let count = 0;

    //現在進行中のchunkの配列
    const chunks: T[][] = [];

    for (const one of source) {
      //新しいchunkの始まりを判断
      if (count % skipCount === 0) {
        chunks.push([]);
      }

      //chunksの中で、sizeを満たしたchunkの数を記録
      let completeChunkCount = 0;

      //各進行中のchunkに値をpush。サイズ条件を満たしたものは個数を記録。
      for (const chunk of chunks) {
        chunk.push(one);
        if (chunk.length === size) {
          yield chunk;
          completeChunkCount++;
        }
      }
      //進行中のchunkは常に先に作られたものから完結するはずなので、
      //chunksから完結した数のchunkを削除
      chunks.splice(0, completeChunkCount);
      count++;
    }

    yield* chunks;
  };

こちらがstackblitzでのデモになります。
https://stackblitz.com/edit/typescript-clbdjt?devToolsHeight=80&file=index.ts

  • 実は挙動が違います。挙げていただいた例ですと、僕の実装の方は最後に[5]も出力されます。rxjsのbufferCountの仕様を見たのですがどちらがご所望の挙動だったでしょうか？

  • 僕の実装の方がおそらくは短いシーケンスでの処理においてはパフォーマンスが悪いです。替わりにsourceシーケンスがどれだけ大きくともメモリ消費量は一定で、無限シーケンスにも対応できる点が優位点になります。短いシーケンスでの処理においてパフォーマンスが悪いのはleseqどころかjsどころかiteratorを使う場合の宿命なのでこれは良しあしだなぁと思います。

以上になります。何か気になるところがございましたらご連絡ください。こういったリアクション自体がうれしくて励みになります！

amay077amay077

返信ありがとうございます！
私の実装は「遅延」でなくその場しのぎだったのでとても勉強になります。

僕の実装の方は最後に[5]も出力されます。

私の実装がバグってますね...。
RxJS の bufferCount も最後の [5] は出力されますし、それが期待される結果だと思います。

これからも使わせて頂きますので、更新を期待しています！
(ちなみにこれまでは linq を使っていました。
これはこれでシンプルで使いやすかったのですが、モジューラブルでない(Tree Shaking 親和性低)のと、若干拡張性に乏しいのでこちらに乗り換えた形です。)